[CF1451E2] Bitwise Queries (Hard Version)

[CF1451E2] Bitwise Queries (Hard Version) - 交互,位运算

Description

一个隐藏的长度为 (n) 的整数数组 (a)，想让 Ashish 去猜，注意 (n) 是 (2) 的整数次幂。三种不同类型的查询。它们分别是：
AND (i) (j): 求元素 (a_i) 和 (a_j) 每一位的 and ((1≤i),(j≤n),(i≠j))
OR (i) (j): 求元素 (a_i) 和 (a_j) 每一位的 or ((1≤i),(j≤n),(i≠j))
XOR (i) (j): 求元素 (a_i) 和 (a_j) 每一位的 xor ((1≤i),(j≤n),(i≠j))

Solution

用 n-1 次操作，计算出 (b_i = a_i oplus a_1, i ge 2)，现在只要求出 (a_1)

如果原数组中有重复，那么要么一定存在一个 (b_i = 0)，我们计算 (a_i And a_1) 就得到了 (a_1)；要么一定存在两个相同的 (b_i)，这种情况类似

否则，一定存在一个 (b_i=1, b_j=n-2)，可以分别得出 (a_1) 的前 (15) 位和最后一位，也就得到了 (a_1)

#include <bits/stdc++.h>
using namespace std;

#define int long long

const int N = 1e6 + 5;

int n, a[N], b[N];

signed main()
{
    ios::sync_with_stdio(false);

    cin >> n;

    int flag = 0, p_1 = 1, p_2 = 1, same_flag = 0, same_a, same_b;

    map<int, int> mp;

    for (int i = 2; i <= n; i++)
    {
        cout << "XOR " << 1 << " " << i << endl;
        cout.flush();
        cin >> b[i];
        if (mp[b[i]])
        {
            same_flag = 1;
            same_a = mp[b[i]];
            same_b = i;
        }
        mp[b[i]] = i;
        if (b[i] == 0)
            flag = i;
        if (b[i] == 1)
            p_1 = i;
        if (b[i] == n - 2)
            p_2 = i;
    }

    if (flag)
    {
        cout << "AND " << 1 << " " << flag << endl;
        cout.flush();
        cin >> a[1];
        for (int i = 2; i <= n; i++)
            a[i] = b[i] ^ a[1];
        cout << "! ";
        for (int i = 1; i <= n; i++)
            cout << a[i] << " ";
        cout << endl;
    }
    else if (same_flag)
    {
        cout << "AND " << same_a << " " << same_b << endl;
        cout.flush();
        cin >> a[same_a];
        a[1] = a[same_a] ^ b[same_a];
        for (int i = 2; i <= n; i++)
            a[i] = b[i] ^ a[1];
        cout << "! ";
        for (int i = 1; i <= n; i++)
            cout << a[i] << " ";
        cout << endl;
    }
    else
    {
        cout << "AND " << 1 << " " << p_1 << endl;
        cout.flush();
        int t1, t2;
        cin >> t1;
        cout << "AND " << 1 << " " << p_2 << endl;
        cout.flush();
        cin >> t2;
        a[1] = ((t1 >> 1) << 1) | (t2 & 1);
        for (int i = 2; i <= n; i++)
            a[i] = b[i] ^ a[1];
        cout << "! ";
        for (int i = 1; i <= n; i++)
            cout << a[i] << " ";
        cout << endl;
    }
}