CFR-685E Bitwise Queries 题解

题目大意

存在一个长度为n的数组（n为2的幂次），每个数的范围在$[0,n-1]$。现在你可以进行n次询问，询问$a[i]\bigoplus a[j] $，$a[i] & a[j]$，$a[i]\mid a[j]$的值，需要你输出这个数组。

解题思路

人生中做的第一道交互题。

好难啊。

这题目分为简单和困难。

唯一的差别就是一个查询n+2次，一个查询n+1次。

所以这边就只写困难版本的了。

首先我们需要知道一个公式$a+b=a\bigoplus b+2\times(a & b)$。

先用n-1次查询，用异或把1和其他的数连接起来。

并且在查询的时候判断是否存在相同的异或值。

如果存在相同的异或值，那么这两个数肯定相同。

那么只需要让这两个相同的数相与或者想或就可以得出这个数的值，然后再异或$a\bigoplus b$，即可得出a[1]。

如果不存在，那么就可以找到$a\bigoplus b==n+1$，即可得出$a& b==0$。

之后在随便找一个数，三个未知数解方程，即可解出a[1]。

得出a[1]之后，再与之前求出的异或值再异或即可求出每一个数的值。

完整代码

#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <queue>
#include <deque>
#include <cstring>
#include <cmath>
#include <stack>
#include <map>
#include <set>
#include <list>
#include <string>
#include <vector>
#include <algorithm>
#include <sstream>
#include <unordered_map>
using namespace std;
#define rep(i,a,n) for (ll i=a;i<=n;i++)
#define per(i,a,n) for (ll i=n;i>=a;i--)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define mp(x,y) make_pair(x,y)
#define pll pair<ll,ll>
#define pii pair<int,int>
#define bg begin
#define rbg rbegin
#define ed end
#define dbg(x) cout << #x << "===" << x << endl
typedef double db;
typedef long long ll;
typedef unsigned long long ull;

int _xor[1 << 17], pos[1 << 17], ans[1 << 17];

int gcd(int a, int b) {
	return !b ? a : gcd(b, a % b);
}

ll qpow(ll a, ll b) {
	ll ans = 1;
	while (b) {
		if (b & 1)	ans *= a;
		a <<= 1, b >>= 1;
	}
	return ans;
}

int q(string s, int i, int j) {
	cout << s << ' ' << i << ' ' << j << endl;
	fflush(stdout);
	int t; cin >> t;
	return t;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	//freopen("D:\\测试用\\in.txt", "r", stdin);
	//freopen("D:\\测试用\\out.txt", "w+", stdout);
	int n; cin >> n;
	memset(pos, -1, sizeof(pos));
	int id1 = -1, id2 = -1;
	rep(i, 2, n) {
		_xor[i] = q("XOR", 1, i);
		if (pos[_xor[i]] != -1)	id1 = pos[_xor[i]], id2 = i;
		pos[_xor[i]] = i;
	}
	if (id1 != -1) {
		ans[id1] = ans[id2] = q("OR", id1, id2);
		ans[1] = _xor[id1] ^ ans[id1];
	}
	else {
		id1 = pos[n - 1];
		id2 = id1 == 2 ? 3 : 2;
		ans[1] = _xor[id1] + _xor[id2] + 2 * q("AND", 1, id2) - (_xor[id1] ^ _xor[id2]) - 2 * q("AND", id1, id2);
		ans[1] /= 2;
	}
	rep(i, 2, n)	ans[i] = _xor[i] ^ ans[1];
	cout << "!" << endl;
	rep(i, 1, n)	cout << ' ' << ans[i];
	cout << endl;
	return 0;
}