【 Codeforces Round #525 (Div. 2) D. Ehab and another another xor problem】交互+思维题

D. Ehab and another another xor problem

题意

这是一道交互题，一开始有两个数a,b,$0<=a,b<=2^{30}$
你一共最多提问62次，每一次用两个数c,d提问
每个提问有三种返回结果
$如果a?c>b?d$ 返回1
$如果a?c=b?d$ 返回0
$如果a?c<b?d$ 返回-1

让你在不超过62次询问后，输出a,b
做法

这个题这个62次询问，可能会给我们一些提示，
我们想一下怎么确定两个数的第一个不相同位
如果两个数大小相同，那么我们只需要从高位到低位不断
$a?2^i$ 如果当前为异或之后a>b 则这一位为0，否则这一位为1
如果两个数不相同，一定是一个大一个小，而且一定是第一个不相同位决定大小
我们先让两个数同时$?0$，这样就能判断两个数的大小关系，
如果当前剩余位a>b
一定是这样的一个01串
a:xxxxxx1xxxxxx
b:xxxxxx0xxxxxx
在这个1，0之前a,b是相同的，之后的不用管，
那么我们让$a?2^{i}b?2^i$
本来a>b,如果到了某一位异或之后返回a<b，那么可以确定a这一位为1，b这一位为0
如果返回a>b,则说明a,b在这一位相同，用之前判相同得方法判断即可，
如果当前剩余位a<b
将上述过程反过来做即可。

而这里要注意一个问题，每次找到一个不同位，用两个变量记录a,b之前的所有1的贡献
每次找到一个不同的位之后，就可以去掉之前的贡献重新判断剩余位两个数的大小关系，
问题就转换为相同性质的子问题，不断往后做就可以了。

代码

#include<stdio.h>
#include<iostream>
using namespace std;
typedef long long ll;
int main()
{
    ll flagc=0,flagd=0;ll ansc=0,ansd=0;int x,k=29;int ff=0;//ff==0 相等 ff==1 大于 ff==-1 小于printf("? 0 0\n");fflush(stdout);scanf("%d",&ff);while(k>=0){
    ll tt=(1LL<<k);if(ff==0){
    printf("? %lld %lld\n",flagc^tt,flagd);fflush(stdout);scanf("%d",&x);if(x==-1){
    ansc=ansc^tt;ansd=ansd^tt;}}else if(ff==-1){
    printf("? %lld %lld\n",flagc^tt,flagd^tt);fflush(stdout);scanf("%d",&x);if(x==1){
    ansd=ansd^tt;flagd=flagd^tt;printf("? %lld %lld\n",flagc,flagd);fflush(stdout);scanf("%d",&ff);}else{
    printf("? %lld %lld\n",flagc^tt,flagd);fflush(stdout);scanf("%d",&x);if(x==-1){
    ansc=ansc^tt;ansd=ansd^tt;}}}else if(ff==1){
    printf("? %lld %lld\n",flagc^tt,flagd^tt);fflush(stdout);scanf("%d",&x);if(x==-1){
    ansc=ansc^tt;flagc=flagc^tt;printf("? %lld %lld\n",flagc,flagd);fflush(stdout);scanf("%d",&ff);}else{
    printf("? %lld %lld\n",flagc^tt,flagd);fflush(stdout);scanf("%d",&x);if(x==-1){
    ansc=ansc^tt;ansd=ansd^tt;}}}k--;}printf("! %lld %lld",ansc,ansd);fflush(stdout);return 0;
}