也许你应该在阅读这篇题解之前读一读 E1的题解
限制从 减少到了 ,于是考虑把 次 操作减少至 次。
注意到,如果原序列中存在两个相等的数,在它们之前做一次 询问就可以简单地得出它们的值。
若不存在,因为有 ,所以原序列是 的一个排列。我们考虑使取到的 ( 同E1题解中的定义) 满足 ,这样 不会在任何一位产生相等,可以少询问一次 。
// 2020.11.22
// Code by LTb
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN=2<<17;
int n;
int a[MAXN];
int ap[MAXN];
signed main()
{
cin>>n;
int xx=0,yy=0,zz;
ap[0]=1;
for (int i=2;i<=n;i++){
cout<<"XOR 1 "<<i<<endl;
cin>>a[i];
if (ap[a[i]] && !xx){ // 此时 a[ap[a[i]]] 与 a[i] 相等
yy=ap[a[i]];
xx=i;
}
ap[a[i]]=i;
}
if (!xx){ // 若不存在相等的数
xx=1;
zz=0;
for (int i=2;i<=n;i++){
if (a[i]==n-2) yy=i;
else if (a[i]==1) zz=i; //随便钦定两个数使它们AND值为0
}
}
else{ // 若存在相等的数
for (int i=1;i<=n;i++)
if (i!=xx && i!=yy) zz=i;
}
int x,y,z;
cout<<"AND "<<xx<<' '<<yy<<endl;
cin>>x;
cout<<"AND "<<xx<<' '<<zz<<endl;
cin>>y;
int qwq=a[2]^a[3],ans=0;
for (int i=15;i>=0;i--){
int tmp1=(x>>i)&1,tmp2=(y>>i)&1;
int tmp4=((a[xx]^a[yy])>>i)&1,tmp5=((a[xx]^a[zz])>>i)&1,tmp6=((a[yy]^a[zz])>>i)&1;
if ((!tmp4) && (!tmp5) && (!tmp6)){
ans|=tmp1<<i;
}
else{
if (!tmp4) ans|=tmp1<<i;
else ans|=tmp2<<i;
}
}
cout<<"! "<<(ans^a[xx]);
for (int i=2;i<=n;i++){
cout<<' '<<(ans^a[i]^a[xx]);
}
cout<<endl;
return 0;
}