cf1088D Ehab and another another xor problem (构造)

时间:2023-03-09 16:27:27
cf1088D Ehab and another another xor problem (构造)

题意:有两数a,b,每次你可以给定c,d询问a xor c和b xor d的大小关系,最多询问62次($a,b<=2^{30}$),问a和b

考虑从高位往低位做,正在做第i位,已经知道了a和b的前i-1位

这样的话,只要让a、c,b、d的前i-1位相同,就和前i-1位没关系了

cf1088D Ehab and another another xor problem (构造)

考虑在第i位上abcd的情况对应的回答(后面的位数都给0),其中~表示与第i位后面的相关

那我可以分别用01 10询问两次,如果是先大后小或是先小后大,就能判断出是00或者11

但如果前后两次相同,那就有可能是01或者10

考虑上一次两次相同的时候是在第j位,具体到底是大于还是小于

然后又因为j+1~i-1位它们a和b都是相同的,所以这个大于还是小于就取决于第i位,所以能得出是01还是10

如果这是第一次相同,那直接再拿00询问一次就可以得到答案

一共61次

 #include<bits/stdc++.h>
#define pa pair<int,int>
#define CLR(a,x) memset(a,x,sizeof(a))
#define MP make_pair
using namespace std;
typedef long long ll;
const int maxn=; inline char gc(){
return getchar();
static const int maxs=<<;static char buf[maxs],*p1=buf,*p2=buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,,maxs,stdin),p1==p2)?EOF:*p1++;
}
inline ll rd(){
ll x=;char c=gc();bool neg=;
while(c<''||c>''){if(c=='-') neg=;c=gc();}
while(c>=''&&c<='') x=(x<<)+(x<<)+c-'',c=gc();
return neg?(~x+):x;
} inline int get(int c,int d){
printf("? %d %d\n",c,d);
fflush(stdout);
return rd();
} int main(){
//freopen("","r",stdin);
int i;
int cp=,dp=;
int a=,b=;
int lst=;
for(i=;i>=;i--){
int v1=get(cp,dp|(<<i)),v2=get(cp|(<<i),dp);
if(v1==v2){
if(lst==) a|=(<<i);
else if(lst==-) b|=(<<i);
else{
if(get(cp,dp)==) a|=(<<i);
else b|=(<<i);
}
lst=v1;
}else if(v1==) a|=(<<i),b|=(<<i);
cp=a,dp=b;
}
printf("! %d %d\n",a,b);
fflush(stdout);
return ; }