Something with XOR Queries [Codeforces Round #440 B]

http://codeforces.com/contest/871/problem/B

インタラクティブ問題。
2つの0～N-1が1つずつある順列p,bが内部で決まっていて、p[b[i]]=iを満たす。
2N回以下の質問で順列pを特定せよ。
質問は「? i j」でp[i] xor b[j]を聞ける。
答えの順列pはユニークでない場合がある。
何通りの順列pがありうるかと、そのうちの1つの順列pを答えよ。

N <= 5*10^3

解法

http://codeforces.com/contest/871/submission/31350603
　
c1[i] := p[i] xor b[i]
c2[i] := p[i] xor b[(i+1)%N]
を2N回の質問で最初に聞く。
　
次に、p[0]を数を全探索する。
b[j] = p[j - 1] xor c2[j - 1];
p[j] = b[j] xor c1[j];
を使えばp[0]から順列p,bを復元できる。
後は、復元した順列が条件を満たすかを判定して満たすならカウントして答え。
　
条件は

• c1とc2をすべて満たすか
• p,bが順列になっているか

int N;
int deb = 0;
int _p[101] = {0,2,1,3 };
int _b[101] = { 0,2,1,3 };
int ask(int i, int j) {
    printf("? %d %d\n", i, j);
    fflush(stdout);

    int res;
    if (deb) res = _p[i] ^ _b[j];
    else cin >> res;

    return res;
}
int a[5010];
int p[5010], b[5010];
typedef long long ll;
void answer(ll n) {
    printf("!\n%lld\n", n);
    rep(i, 0, N) {
        if (i) printf(" ");
        printf("%d", a[i]);
    } printf("\n");
}
//---------------------------------------------------------------------------------------------------
int c1[5050], c2[5050];
int cnt[5050];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;

    rep(i, 0, N) c1[i] = ask(i, i);
    rep(i, 0, N) c2[i] = ask(i, (i + 1) % N);

    ll n = 0;
    rep(ini, 0, N) {
        p[0] = ini;
        b[0] = ini ^ c1[0];

        rep(j, 1, N) {
            b[j] = p[j - 1] ^ c2[j - 1];
            p[j] = b[j] ^ c1[j];
            
        }

        if (c2[N - 1] != (p[N - 1] ^ b[0])) continue;

        int ok;

        ok = 1;
        rep(i, 0, N) if (!(0 <= p[i] and p[i] < N)) ok = 0;
        rep(i, 0, N) if (!(0 <= b[i] and b[i] < N)) ok = 0;
        if (!ok) continue;

        rep(i, 0, N) cnt[i] = 0;
        rep(i, 0, N) cnt[p[i]]++;
        ok = 1;
        rep(i, 0, N) if (cnt[i] != 1) ok = 0;
        if (!ok) continue;

        rep(i, 0, N) cnt[i] = 0;
        rep(i, 0, N) cnt[b[i]]++;
        ok = 1;
        rep(i, 0, N) if (cnt[i] != 1) ok = 0;
        if (!ok) continue;

        ok = 1;
        rep(i, 0, N) {
            if (p[b[i]] != i) {
                ok = 0;
            }
        }
        if (!ok) continue;

        n++;
        rep(i, 0, N) a[i] = p[i];
    }

    answer(n);
}