Número de valores distintos (Editorial)

Idea

Tenemos un arreglo oculto $a$ de longitud $n$. Cada consulta es una permutación de índices, y como respuesta aprendemos para cada elemento cuántos de sus vecinos (en el orden elegido) tienen el mismo valor. Necesitamos encontrar la cantidad de valores distintos en el arreglo usando como máximo \frac{n}{2} + 1 consultas.

Observación clave 1: recuperar igualdades entre vecinos

Supongamos que hicimos una consulta con alguna permutación y recibimos el arreglo $b$. Sea \text{eq}[i] = 1 si p_i = p_{i+1}, y $0$ en caso contrario. Entonces:

A partir de esto podemos recuperar secuencialmente todos los $\text{eq}[i]$:

Así, de una sola consulta aprendemos, para cada par de elementos adyacentes en nuestra permutación, si tienen el mismo valor en el arreglo $a$.

Observación clave 2: cubrir todos los pares

Para determinar completamente qué índices comparten el mismo valor, cada par de índices $(i,j)$ debe aparecer como vecinos en al menos una consulta.

Este es el problema clásico de planificación de torneos round-robin: $n$ jugadores juegan contra todos los demás, y en cada ronda cada jugador juega exactamente un partido. Para $n$ par se necesitan n - 1 rondas, pero a nosotros nos bastan \frac{n}{2} rondas donde cada ronda da una permutación cuyos pares adyacentes cubren todos los pares necesarios.

La construcción es la siguiente: si $n$ es impar, completamos a m = n + 1 (par). Luego, para cada ronda k = 0, 1, \ldots, \frac{m}{2} - 1 construimos una permutación comenzando con el elemento $k$, alternando elementos k - 1, k + 1, k - 2, k + 2, \ldots, terminando con el elemento k + \frac{m}{2} (todos los índices se toman módulo $m$; si un índice es $\ge n$, lo omitimos).

Esto da exactamente \frac{n}{2} (redondeado hacia arriba) consultas, lo cual cumple con el límite de \frac{n}{2} + 1.

Unión de resultados con DSU

Mantenemos una estructura DSU (Disjoint Set Union). Después de cada consulta, si \text{eq}[i] = 1, unimos los índices $q[i]$ y q[i+1] (donde $q$ es nuestra permutación). Después de todas las consultas, el número de componentes en el DSU es la respuesta — la cantidad de valores distintos en el arreglo.

¿Por qué es correcto?

Dos índices $i$ y $j$ terminan en el mismo componente del DSU si y solo si a_i = a_j. Si a_i = a_j, en la consulta donde son vecinos obtenemos \text{eq} = 1 y los unimos. Si a_i \neq a_j, nunca se unen porque en cada consulta donde son vecinos \text{eq} = 0.

La transitividad la garantiza el DSU: si a_i = a_j y a_j = a_k, los tres terminan en el mismo componente aunque el par $(i,k)$ nunca haya sido verificado directamente como vecinos.

Complejidad

Número de consultas: O\!\left(\frac{n}{2}\right).

Construcción de permutaciones: O(n^2).

DSU con heurísticas: O(n \cdot \alpha(n)) por consulta.

En total: O(n^2), lo cual es rápido para 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;
}