Кількість різних чисел (Розбір)

Ідея

Маємо прихований масив $a$ довжини $n$. Кожен запит — це перестановка індексів, а у відповідь ми дізнаємось для кожного елемента, скільки його сусідів (у вибраному порядку) мають таке саме значення. Потрібно знайти кількість різних чисел у масиві за не більше ніж \frac{n}{2} + 1 запитів.

Ключове спостереження 1: відновлення рівностей сусідів

Нехай ми зробили запит з перестановкою і отримали масив $b$. Позначимо \text{eq}[i] = 1, якщо p_i = p_{i+1}, і $0$ інакше. Тоді:

З цього можна послідовно відновити всі $\text{eq}[i]$:

Отже, з одного запиту ми дізнаємось для кожної пари сусідніх елементів у нашій перестановці, чи мають вони однакове значення в масиві $a$.

Ключове спостереження 2: покриття всіх пар

Щоб повністю визначити, які індекси мають однакове значення, потрібно, щоб кожна пара індексів $(i,j)$ хоча б раз опинилась на сусідніх позиціях у якомусь запиті.

Це класична задача побудови розкладу турніру (round-robin): $n$ гравців грають один з одним, і за один тур кожен грає рівно один матч. Для парного $n$ потрібно рівно n - 1 турів, але нам достатньо \frac{n}{2} турів, де кожен тур дає перестановку, в якій пари сусідів покривають усі потрібні пари.

Конструкція така: якщо $n$ непарне, доповнюємо до m = n + 1 (парного). Далі для кожного туру k = 0, 1, \ldots, \frac{m}{2} - 1 будуємо перестановку за правилом: починаємо з елемента $k$, потім чергуємо елементи k - 1, k + 1, k - 2, k + 2, \ldots, закінчуючи елементом k + \frac{m}{2} (усі індекси беруться за модулем $m$, а якщо індекс $\ge n$ — пропускаємо його).

Це дає рівно \frac{n}{2} (з округленням вгору) запитів, що вкладається в ліміт \frac{n}{2} + 1.

Об'єднання результатів через DSU

Підтримуємо структуру "система неперетинних множин" (DSU). Після кожного запиту, якщо \text{eq}[i] = 1, об'єднуємо індекси $q[i]$ та q[i+1] (де $q$ — наша перестановка). Після всіх запитів кількість компонент у DSU і є відповіддю — кількістю різних чисел у масиві.

Чому це коректно?

Два індекси $i$ та $j$ потраплять в одну компоненту DSU тоді і тільки тоді, коли a_i = a_j. Якщо a_i = a_j, то в тому запиті, де вони сусіди, ми отримаємо \text{eq} = 1 і об'єднаємо їх. Якщо a_i \neq a_j, вони ніколи не будуть об'єднані, бо в кожному запиті, де вони сусіди, \text{eq} = 0.

Транзитивність забезпечує DSU: якщо a_i = a_j і a_j = a_k, то всі три потраплять в одну компоненту, навіть якщо пара $(i,k)$ безпосередньо не перевірялась як сусіди.

Асимптотика

Кількість запитів: O\!\left(\frac{n}{2}\right).

Побудова перестановок: O(n^2).

DSU з евристиками: O(n \cdot \alpha(n)) на запит.

Загалом: O(n^2), що при n \le 2 \cdot 10^3 працює швидко.

#include <bits/stdc++.h>
using namespace std;

struct DSU {
    vector<int> p, sz;
    DSU(int n = 0) {
        p.resize(n);
        sz.assign(n, 1);
        iota(p.begin(), p.end(), 0);
    }
    int find(int v) {
        return p[v] == v ? v : p[v] = find(p[v]);
    }
    void unite(int a, int b) {
        a = find(a); b = find(b);
        if (a == b) return;
        if (sz[a] < sz[b]) swap(a, b);
        p[b] = a;
        sz[a] += sz[b];
    }
};

vector<vector<int>> build_queries(int n) {
    int m = n + n % 2;
    vector<vector<int>> queries;
    for (int k = 0; k < m / 2; k++) {
        vector<int> q;
        auto add = [&](int x) {
            x = (x % m + m) % m;
            if (x < n) q.push_back(x);
        };
        add(k);
        for (int t = 1; t <= m / 2 - 1; t++) {
            add(k - t);
            add(k + t);
        }
        add(k + m / 2);
        queries.push_back(q);
    }
    return queries;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;

    DSU dsu(n);
    auto queries = build_queries(n);

    for (auto &q : queries) {
        cout << "? ";
        for (int i = 0; i < n; i++) {
            if (i) cout << ' ';
            cout << q[i] + 1;
        }
        cout << endl;

        vector<int> b(n);
        for (int i = 0; i < n; i++) cin >> b[i];

        if (n == 1) continue;

        vector<int> eq(n - 1);
        eq[0] = b[0];
        for (int i = 1; i < n - 1; i++)
            eq[i] = b[i] - eq[i - 1];

        for (int i = 0; i < n - 1; i++)
            if (eq[i] == 1)
                dsu.unite(q[i], q[i + 1]);
    }

    int ans = 0;
    for (int i = 0; i < n; i++)
        if (dsu.find(i) == i) ans++;

    cout << "! " << ans << endl;
    return 0;
}