人生第一道交互题 & 非传统题qwq

Description

This is an interactive problem!

Ehab plays a game with Laggy. Ehab has 2 hidden integers (a,b), Laggy can ask a pair of integers (c, d) and Ehab will reply with:

1 if $a \oplus c>b \oplus d$
0 if $a \oplus c=b \oplus d$
-1 if $a \oplus c<b \oplus d$

Operation $a \oplus b$ is the bitwise-xor operation of two numbers a and b

Laggy should guess $(a,b)$ with at most 62 questions. You’ll play this game. You’re Laggy and the interactor is Ehab.

It’s guaranteed that $0 \leq a,b<2^{30}$

Samples

Input #1

1
2
3

1
-1
0

Output #1

Solution

考虑从高位到低位依次确定$a,b$的二进制组成, 假设当前已确定的二进制组成为$A, B$.

首先用一次询问$(0,0)$求出$a,b$的大小关系, 令其为$k$.

然后我们用这个$k$来维护当前$a \oplus A$和$b \oplus B$的大小关系.

对于每一位, 我们首先用一个询问$(A \oplus 2^i, B \oplus 2^i)$, 如果得到的大小关系等于$k$, 则说明这两个二进制位相等,不需要更新$k$ , 否则不等.

如果相等, 那么继续询问$(A \oplus 2^i, B)$, 如果结果为$1$, 说明两个数都不含第$i$位, 若为-1，则说明两数都含第$i$位, 然后更新$A,B$

如果不等, 得到的大小关系为1，则$a$含有第$i$位, 否则$b$含有之, 更新$A,B$

这时候$k$的值就可能发生改变, 所以应再用一个询问$(A,B)$来更新$k$的值.

Code

/* Headers */
#include<algorithm>
#include<iostream>
#include<cstring>
#include<climits>
#include<cstdio>
#include<cctype>
#include<vector>
#include<cmath>
#include<queue>
#include<stack>
#include<map>
#define FOR(i,a,b,c) for(int i=(a);i<=(b);i+=(c))
#define ROF(i,a,b,c) for(int i=(a);i>=(b);i-=(c))
#define FORL(i,a,b,c) for(long long i=(a);i<=(b);i+=(c))
#define ROFL(i,a,b,c) for(long long i=(a);i>=(b);i-=(c))
#define FORR(i,a,b,c) for(register int i=(a);i<=(b);i+=(c))
#define ROFR(i,a,b,c) for(register int i=(a);i>=(b);i-=(c))
#define lowbit(x) x&(-x)
#define LeftChild(x) x<<1
#define RightChild(x) (x<<1)+1
#define RevEdge(x) x^1
#define FILE_IN(x) freopen(x,"r",stdin);
#define FILE_OUT(x) freopen(x,"w",stdout);
#define CLOSE_IN() fclose(stdin);
#define CLOSE_OUT() fclose(stdout);
#define IOS(x) std::ios::sync_with_stdio(x)
#define Dividing() printf("-----------------------------------\n");
namespace FastIO{
    const int BUFSIZE = 1 << 20;
    char ibuf[BUFSIZE],*is = ibuf,*its = ibuf;
    char obuf[BUFSIZE],*os = obuf,*ot = obuf + BUFSIZE;
    inline char getch(){
        if(is == its)
            its = (is = ibuf)+fread(ibuf,1,BUFSIZE,stdin);
        return (is == its)?EOF:*is++;
    }
    inline int getint(){
        int res = 0,neg = 0,ch = getch();
        while(!(isdigit(ch) || ch == '-') && ch != EOF)
            ch = getch();
        if(ch == '-'){
            neg = 1;ch = getch();
        }
        while(isdigit(ch)){
            res = (res << 3) + (res << 1)+ (ch - '0');
            ch = getch();
        }
        return neg?-res:res;
    }
    inline void flush(){
        fwrite(obuf,1,os - obuf,stdout);
        os = obuf;
    }
    inline void putch(char ch){
        *os++ = ch;
        if(os == ot)	flush();
    }
    inline void putint(int res){
        static char q[10];
        if(res == 0) putch('0');
        else if(res < 0){putch('-');res = -res;}
        int top = 0;
        while(res){
            q[top++] = res % 10 + '0';
            res /= 10;
        }
        while(top--)	putch(q[top]);
    }
    inline void space(bool x){
    	if(!x) putch('\n');
    	else putch(' ');
    }
}
inline void read(int &x){
    int rt = FastIO::getint();
    x = rt;
}
inline void print(int x,bool enter){
    FastIO::putint(x);
    FastIO::flush();
    FastIO::space(enter);
}
/* definitions */
int a, b;
bool AgeqB = true;
/* functions */
inline int Query(int x, int y, int res = 0) {
	printf("? %d %d\n", x, y);
	fflush(stdout);
	scanf("%d", &res);
	return res;
}
inline int Answer(int x, int y) {
	printf("! %d %d\n", x, y);
	fflush(stdout); exit(0);
}
int main(int argc,char *argv[]){
	if(Query(a, b) == -1) AgeqB = false;
	ROF(i, 29, 0, 1) {
		int x = Query(a ^ (1 << i), b);
		int y = Query(a, b ^ (1 << i));
		if(x == y) {
			if(AgeqB) a ^= (1 << i);
			else b ^= (1 << i);
			AgeqB = (x == 1);
		}
		else if(x == -1 && y == 1) a ^= (1 << i), b ^= (1 << i);
	}	
	Answer(a, b);	
	return 0;
}

Codeforces1088D题解