IZhO '19 P4 - Xoractive

#include "interactive.h"
#include <map>

using namespace std;

vector<int> guess(int n) {
    int x = ask(1), maxBit = 0;
    while ((1 << (maxBit+1)) <= n-1) ++maxBit;
    auto getVals = [&x](vector<int> v) {
        vector<int> p = get_pairwise_xor(v);
        v.push_back(1);
        vector<int> q = get_pairwise_xor(v);
        vector<int> vals;
        for (int i = 0, j = 0; j < q.size(); ++j) {
            if (i < p.size() && p[i] == q[j]) ++i;
            else if (q[j]) vals.push_back(q[j] ^ x);
        }
        return vals;
    };

    map<int, int> where; // value to index
    for (int i = 0; i <= maxBit; ++i) {
        vector<int> v;
        for (int j = 2; j <= n; ++j) {
            if ((j-1) & (1 << i)) v.push_back(j);
        }
        vector<int> res = getVals(v);
        for (int y : res) where[y] |= (1 << i);
    }

    vector<int> ans(n); ans[0] = x;
    for (auto [y, i] : where) ans[i] = y;
    return ans;
}