Official

G - Odd or Even Editorial by en_translator


First, we describe how to solve it when \(N = K + 1\). We denote by \(s_i\) the response to the query.

We ask \((i, i+1, \dots, i+K-1)\) in the \(i\)-th query (if an index exceeds \(N\), subtracting \(N\) from it). For example, for \(N=4,K=3\), we ask the following queries:

\[ \begin{aligned} A_1 + A_2 + A_3 &= s_1\\ A_2 + A_3 + A_4 &= s_2\\ A_3 + A_4 + A_1 &= s_3\\ A_4 + A_1 + A_2 &= s_4\\ \end{aligned} \]

In \(N\) queries, each of \(A_1, A_2, \dots, A_N\) occurs \(K\) times in the left hand side. Here, since \(K\) is odd, the parity of \(A_1 + A_2 + \dots +A_N\) coincides with that of \(s_1 + s_2 + \dots + s_N\). Thus, taking the sum of the both hand sides yields the parity of \(A_1 + A_2 + \dots + A_N\). Then, taking differences appropriately determines all of \(A_1, A_2, \dots, A_N\) one by one. For example, when \(N=4, K=3\),

\[A_4 = (A_1 + A_2 + A_3 + A_4) - (A_1 + A_2 + A_3),\]

so the parity of \(A_4\) is determined by \(s_1\) and the parity of \(A_1 + A_2 + A_3 + A_4\). (Same applies to \(A_1\), \(A_2\), and \(A_3\).) Thus, the problem is solved for \(N=K+1\).

Actually, this solution can be applied to a general \(N\). First, as we did for \(N=K+1\), consume \(K+1\) queries to determine \(A_1, A_2, \dots, A_{K+1}\). Next, for \(i = K+2, K+3, \dots, N\), ask \((1, 2, \dots, K-1, i)\) in the \(i\)-th query. Then,

\[ \begin{aligned} A_i = s_i - (A_1 + A_2 + \dots + A_{K-1}), \end{aligned} \]

so the parity of \(A_i\) is determined by \(A_1, A_2, \dots, A_{K-1}, s_i\). Repeating this, one can determine all the elements of \(A\).
Hence, the problem has been solved with \(N\) queries.

  • Sample code (C++)
#include <bits/stdc++.h>
using namespace std;

void out(vector<int> v) {
  for (unsigned i = 0; i < v.size(); i++) {
    cout << v[i] << " \n"[i + 1 == v.size()];
  }
}
int main() {
  int N, K;
  cin >> N >> K;
  auto send = [&](vector<int> v) {
    for (auto& x : v) x++;
    cout << "? ", out(v);
    cout.flush();
    int x;
    cin >> x;
    return x;
  };
  vector<int> ans(N);
  {
    int r = 0;
    for (int i = 0; i < K + 1; i++) {
      vector<int> v;
      for (int j = 0; j < K + 1; j++)
        if (i != j) v.push_back(j);
      ans[i] = send(v);
      r ^= ans[i];
    }
    for (int i = 0; i < K + 1; i++) ans[i] ^= r;
  }
  {
    vector<int> v(K);
    int s = 0;
    for (int i = 0; i < K - 1; i++) v[i] = i, s ^= ans[i];
    for (int i = K + 1; i < N; i++) {
      v.back() = i;
      int t = send(v);
      ans[i] = s ^ t;
    }
  }
  cout << "! ", out(ans);
  cout.flush();
}

posted:
last update: