Not able to solve this problem during the contest (virtual participation).
The first observation is that if we can identify $N-1$ balls of which half is blue and the other half is red, then with these $N - 1$ balls we can identify the color of the rest $N+1$ balls.
It's not hard to note that if there are more blue balls than red balls among balls numbered from $l$ to $l + N - 1$ but less among balls numbered from $l + 1$ to $l + N$, we then know that
- The $l$-th ball and the $l+N$-th ball must be of different colors.
- The $l$-th ball must be blue and the $l+N$-th ball must be red.
- There are equal number of blue and red balls among balls numbered from $l + 1$ to $l+N - 1$.
The problem is whether such $l$ even exists? The answer is ,fortunately, YES.
Here comes the second interesting observation:
Let's assume without loss of generality, there are more blue balls than red balls among the first $N$ balls, then there must be more red balls among the last $N$ balls. So such $l$ as described above must exist, and we can find one using binary search which costs at most $log_2 N + 1$ queries. When the binary search finishes, we get $l$ and the color of the $l$-th and $l+N$-th balls.
When $l$ is found, for each ball numbered from $1$ to $l - 1$ or from $l + N + 1$ to $2N$, we can know its color with a query. Note that exactly half of these $N - 1$ known balls are blue, so we can use these balls to identify color of balls numbered from $l + 1$ to $l + N -1$ in a similar way.
code
int main() { int n; cin >> n; auto ask = [&](int l) { cout << '?'; for (int i = 0; i < n; i++) { cout << ' ' << l + i; } cout << endl; string res; cin >> res; return res.front(); }; char ml = ask(1); int l = 1, r = n + 1;
while (r - l > 1) {
int mid = l + (r - l) / 2;
if (ask(mid) == ml) {
l = mid;
} else {
r = mid;
}
}
vectorans(2 * n + 1);
ans[l] = ml;
ans[l + n] = ml == 'R' ? 'B' : 'R';auto ask2 = [&](int pos) {
cout << '?';
for (int i = 1; i < n; i++) {
cout << ' ' << l + i;
}
cout << ' ' << pos << endl;
string res;
cin >> res;
return res.front();
};
// [l + 1, l + n)
rng (i, 1, 2 * n + 1) {
if (i < l || i > l + n) {
ans[i] = ask2(i);
}
}
auto ask3 = [&](int pos) {
cout << '?';
rng (i, 1, 2 * n + 1) {
if (i < l || i > l + n) {
cout << ' ' << i;
}
}
cout << ' ' << pos << endl;
string res;
cin >> res;
return res.front();
};
rng (i, l + 1, l + n) {
ans[i] = ask3(i);
}
cout << "! ";
for (int i = 1; i <= 2 * n; i++) {
cout << ans[i];
}
cout << ' ';
return 0;
}