CF1088D Ehab and another another xor problem 做题记录

交互题，系统有两个整数 $(a,b)$，你每次可以询问一组整数 $(c,d)$，系统会回答：

• $1$ 如果 $a\oplus c>b\oplus d$
• $0$ 如果 $a\oplus c=b\oplus d$
• $-1$ 如果 $a\oplus c<b\oplus d$

其中操作 $a\oplus b$ 表示 $a$ 和 $b$ 按位异或。

你需要在询问不超过 $62$ 次之后输出 $(a,b)$ 的值，保证 $0\le a, b < 2^{30}$。

首先显然可以询问一次得到 $a,b$ 的大小关系 $f$，接下来分类讨论：

• 若 $f=0$，那么 $a$ 和 $b$ 相等，从高位向低位依次枚举，显然第 $i$ 位为 $1$ 当且仅当 $a>(b\oplus 2^i)$。这样就可以用 $30$ 次询问确定 $a$ 和 $b$；

• 若 $f\not=0$，那么从高位向低位依次枚举。枚举到第 $i$ 位时设当前（确定了前面的位的）答案为 $A$ 和 $B$，$a\oplus A$ 和 $b\oplus B$ 的大小关系为 $F$。

  显然刚开始 $A=0,B=0,F=f$。

  枚举到第 $i$ 位时，询问 $(a\oplus A\oplus 2^i)$ 和 $(b\oplus B\oplus 2^i)$ 的大小关系，即询问两个数第 $i$ 位和更低位都异或上 $2^i$ 的大小关系。设询问的结果为 $E$，分类讨论：

  • 若 $E=F$，那么 $a$ 和 $b$ 的第 $i$ 位相等，这时若 $(a\oplus A)>(b\oplus B\oplus 2^i)$ 那么 $a$ 和 $b$ 的第 $i$ 位为 $1$，因为 $(a\oplus A)$ 和 $(b\oplus B)$ 的最高位都是第 $i$ 位，这一位均为 $1$ 那么异或 $2^i$ 相当于消去最高位，显然会变得比另一个小；
  • 若 $E\not=F$，那么 $a$ 和 $b$ 的第 $i$ 位不相等，这时若 $F=1$ 那么 $a$ 的第 $i$ 位为 $1$，否则 $b$ 的第 $i$ 位为 $1$。更新完 $A$ 和 $B$ 之后再问一次 $(a\oplus A)$ 和 $(b\oplus B)$ 的大小关系来更新 $F$，注意若此时 $F$ 更新成 $0$ 那么剩下的位就要按照 $f=0$ 情况的方法处理。

  代码如下：

  // Problem: CF1088D Ehab and another another xor problem
  // Contest: Luogu
  // URL: https://www.luogu.com.cn/problem/CF1088D
  // Memory Limit: 250 MB
  // Time Limit: 1000 ms
  // 
  // Powered by CP Editor (https://cpeditor.org)
  
  #include <iostream>
  #include <cstdio>
  
  using namespace std;
  
  const int N=29;
  
  int a,b;
  
  inline int que(int c,int d)
  {
  	printf("? %d %d\n",c,d);
  	fflush(stdout);
  	int x;
  	scanf("%d",&x);
  	return x;
  }
  
  int main()
  {
  	int f=que(0,0);
  	int srt=N;
  	if(f!=0)
  	{
  		for(int i=N;i>=0;i--)
  		{
  			int val=1<<i;
  			int pre=que(a^val,b^val);
  			if(pre!=f)
  			{
  				if(f==1) a|=val;
  				else b|=val;
  				f=que(a,b);
  				if(f==0)
  				{
  					srt=i-1;
  					break;
  				}
  			}
  			else if((f==1&&que(a^val,b)==-1)||(f==-1&&que(a,b^val)==1)) a|=val,b|=val;
  		}
  	}
  	for(int i=srt;i>=0;i--)
  	{
  		int val=1<<i;
  		if(que(a,b^val)==1) a|=val,b|=val;
  	}
  	printf("! %d %d\n",a,b);
  	fflush(stdout);
  	return 0;
  }