cfD. Ehab and another another xor problem(思維)

題意

題目鏈接

系統中有兩個數\((a, b)\)，請使用\(62\)以內次詢問來確定出\((a, b)\)

每次可以詢問兩個數\((c, d)\)

若\(a \oplus c > b \oplus d\)返回\(1\)

若\(a \oplus c = b \oplus d\)返回\(0\)

若\(a \oplus c < b \oplus d\)返回\(-1\)

保證/需要保證\(0 \leqslant a, b, c, d, < 2^{30}\)

Sol

嚴重懷疑自己小學數學沒學好，剛開始以為\(a, b, c, d < 2^{30}\)說明每位只有兩次機會，然後模擬了\(4 * 4 * 3\)種情況後發現怎麼都搞不了，今天看std發現是每位詢問兩次後還有額外的兩次詢問機會qwqqqqq

如果多兩次機會的話就能搞了，因為我打比賽的時候遇到的問題就是如何確定出當前兩位和除去這兩位之後的大小關係。這樣我們可以上來先詢問出\((a, b)\)的大小關係，然後xjb特判一下。。

標算好神仙啊。。

#include<bits/stdc++.h> 
#define Pair pair<int, int>
#define MP(x, y) make_pair(x, y)
#define fi first
#define se second
//#define int long long 
#define LL long long 
#define rg register 
#define pt(x) printf("%d ", x);
#define Fin(x) {freopen(#x".in","r",stdin);}
#define Fout(x) {freopen(#x".out","w",stdout);}
using namespace std;
const int MAXN = 1e6 + 10, INF = 1e9 + 10, mod = 1e9 + 7;
const double eps = 1e-9;
int Query(int c, int d) {
    printf("? %d %d\n", c, d); fflush(stdout);
    int opt; scanf("%d", &opt); return opt;
}
int a, b, flag, B = 29;
main() {
    flag = Query(0, 0);
    for(int i = B; i >= 0; i--) {
        int x = Query(a | (1 << i), b), y = Query(a, b | (1 << i));
        if(x == y) {
            if(flag == 1) a |= (1 << i);
            else b |= (1 << i); 
            flag = x;
        } else if(x == -1) {
            a |= (1 << i);
            b |= (1 << i);
        }
    }
    printf("! %d %d", a, b);
    return 0;
}