The penguin's game [Codeforces Round #427 (Div. 2) E]

http://codeforces.com/contest/835/problem/E

概要

インタラクティブ問題。
N要素の未知の配列がある。
これは2要素のみYで他は全てXである。
最大19回「指定の要素のxor和を返す質問」ができる。
Yが書かれている要素番号を答えよ。

解説

http://codeforces.com/contest/835/submission/29088591
　
公式解説とkmjpさんの解法を見て理解した。
　
質問をすると4パターンの返答がありうる
1. 質問の個数が偶数で、Yの要素が偶数なら「0」
2. 質問の個数が偶数で、Yの要素が奇数なら「x xor y」
3. 質問の個数が奇数で、Yの要素が偶数なら「x」
4. 質問の個数が奇数で、Yの要素が奇数なら「y」
　
まず、10回質問を使って、答えのbit-wise diffを取る。
具体的には以下の手続きをする

for(i = 0...9) {
    vector<int> v = {i番目のビットが1である要素番号};
    if(ask(v)の答えが奇数) {
        // 2つの答えでは、i番目のビットは異なっている
    }
}

diff変数を用意する。
もう一つ、maxbit変数として異なっている最上位ビットを保持しておく。
　
次に、答えのうち小さい方を9回で特定する。
探す領域はmaxbitビット目が0であるものだけとする。
こうすることで、2つの答えのうち1つだけを対象とした探索ができる。
あとは、上記の手続きと同じような感じで答えを求めて、diffでもう一つの答えを見つけたら、それを答える。

int N, X, Y;
//---------------------------------------------------------------------------------------------------
int ask(vector<int> &v) {
    printf("? %d", v.size());
    fore(i, v) printf(" %d", i + 1);
    printf("\n");
    fflush(stdout);

    int res; cin >> res;
    return res;
}
void answer(int a, int b) {
    printf("! %d %d\n", a + 1, b + 1);
    fflush(stdout);
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> X >> Y;

    int diff = 0;
    int maxbit = -1;
    rep(i, 0, 10) {
        vector<int> v;
        rep(j, 0, N) if (j & (1 << i)) v.push_back(j);
        if (v.empty()) continue;
        int res = ask(v);
        if (res == (X^Y) || res == Y) {
            diff |= (1 << i);
            maxbit = i;
        }
    }

    int a1 = 0;
    rep(i, 0, 10) if (i != maxbit) {
        vector<int> v;
        rep(j, 0, N) if (j & (1 << i)) if ((j & (1 << maxbit)) == 0) v.push_back(j);
        if (v.empty()) continue;
        int res = ask(v);
        if (res == (X^Y) || res == Y) a1 |= (1 << i);
    }

    answer(a1, a1 ^ diff);
}