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: