XOR Guessing

Created by LXC on Wed Jul 5 09:29:54 2023

https://codeforces.com/problemset/problem/1207/E

ranting: 1900

tag: bitmasks, interactive, math

problem

有一个小于$2^{14}$的非负整数x需要我们猜测。

我们只能查询两次，每次查询需要我们给出100个数$a_1, a_2, \cdots, a_{100}$。然后后台会随机选取一个数$a_i$然后将$x\oplus a_i$返回。

$\oplus$ 为异或

我们查询时上传的共200个数不能相同，且为小于$2^{14}$的非负整数。

solution

对于位运算，我们可以考虑拆位。每一位的运算结果独立。

我们知道任何数异或0都为本身。所以第一次查询可以让高7位的数全为0，这样无论异或的是哪个数我们都会得到x的高7位。

同理，第二次查询让低7位为0，就得到了低7位，然后将其拼接就得到了x

code

#include <bits/stdc++.h>
#define SINGLE_INPUT
#define ll long long
#define ull unsigned long long
#define N 500005
#define MOD 998244353
using namespace std;

// int t = 1212;

int q1() {
    cout << "? ";
    for (int i = 1; i <= 100; i++) {
        cout << i << " ";
    }
    cout << endl;
    // int rt = t ^ 56;
    int rt;
    cin >> rt;
    return rt;
}

int q2() {
    cout << "? ";
    for (int i = 1; i <= 100; i++) {
        cout << (i << 7) << " ";
    }
    cout << endl;
    // int rt = t ^ (37 << 7);
    int rt;
    cin >> rt;
    return rt;
}

void sol() {
    int x = q1(), y = q2();
    cout << "! " << (x >> 7 << 7) + y % (1 << 7) << endl;
}

int main() {
    cout << setprecision(15) << fixed;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}