Ehab and another another xor problem

Created by LXC on Tue Apr 2 08:41:13 2024

https://codeforces.com/problemset/problem/1088/D

ranting: 2000

tag: bitmasks, constructive algorithms, implementation, interactive

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 以输出答案，不要忘了在输出答案后清除缓冲区

输出 ? c d 以询问，$c$ 和 $d$ 都应该是小于 $2^{30}$ 的非负整数，不要忘了在输出每一次询问后清除缓冲区

你可以用下列操作来清除缓冲区：

• C++：fflush(stdout)
• Java：System.out.flush()
• Python：stdout.flush()
• Pascal：fflush(stdout)
• 对于其它语言请参考文档

solution

设整数x的二进制第i位为$x_i$

对于两个数$x,y$，$x>y$说明x的二进制高位向低位遍历，一定存在$x_i > y_i$

我们构造c和d，最终让a=c和b=d，我们高位开始逐位构造c和d。

初始时c=0,d=0。

首先判断a和b的大小关系：

• $a\oplus c = b \oplus d$
  • 说明$a_i = b_i$,我们要进一步判断是0还是1，如果$a_i < b_i\oplus 1$，则$a_i = b_i = 0$，否则$a_i = b_i = 1$，然后继续构造下一位。
• $a\oplus c < b \oplus d$
  • 存在$a_i < b_i$，于是一旦出现$a_i\oplus 1 > b_i \oplus 1$，这个时候$a_i = 0, b_i = 1$，然后重新判断a和b低位i位的大小，继续构造。
• $a\oplus c > b \oplus d$
  • 存在$a_i > b_i$，于是一旦出现$a_i\oplus 1 < b_i \oplus 1$，这个时候$a_i = 1, b_i = 0$，然后重新判断a和b低位i位的大小，继续构造。

初始判断a和b的大小需要一次操作，从0到29位每一步需要两次操作，共计61次操作。

code

#include <bits/stdc++.h>
#define SINGLE_INPUT
#define ll long long
#define ull unsigned long long
#define N 500005
#define MOD 998244353
using namespace std;

template<class t,class u> ostream& operator<<(ostream& os,const pair<t,u>& p) {
    return os<<'['<<p.first<<", "<<p.second<<']';
}
template<class t> ostream& operator<<(ostream& os,const vector<t>& v) {
    os<<'['; int s = 1;
    for(auto e:v) { if (s) s = 0; else os << ", "; os << e; }
    return os<<']';
}
template<class t,class u> ostream& operator<<(ostream& os,const map<t,u>& mp){
    os<<'{'; int s = 1;
    for(auto [x,y]:mp) { if (s) s = 0; else os << ", "; os<<x<<": "<<y; }
    return os<<'}';
}

ll ha = 10234132, hb = 1979843;
int cnt = 0;
int ask(ll c, ll d) {
    cnt++;
    cout << "? " << c << " " << d << endl;
    int rt;
    // if ((ha^c) == (hb^d)) rt = 1;
    // if ((ha^c) > (hb^d)) rt = 1;
    // if ((ha^c) < (hb^d)) rt = -1;
    cin >> rt;
    return rt;
}

void sol() {
    ll a = 0, b = 0;
    int p = ask(0, 0);
    for (int i=29; i>=0; i--) {
        ll x = 1<<i;
        if (p == 1) {
            int rt = ask(a|x, b|x);
            if (rt == -1) {
                a |= x;
                p = ask(a, b);
            } else {
                rt = ask(a|x, b);
                if (rt == -1) {
                    a |= x;
                    b |= x;
                }
            }
        } else if (p == -1) {
            int rt = ask(a|x, b|x);
            if (rt == 1) {
                b |= x;
                p = ask(a, b);
            } else {
                rt = ask(a, b|x);
                if (rt == 1) {
                    a |= x;
                    b |= x;
                }
            }
        } else {
            int rt = ask(a|x, b);
            if (rt == -1) {
                a |= x;
                b |= x;
            }
        }
    }
    cout << "! " << a << " " << b << endl;
    // cout << "cnt " << cnt << endl;
}

int main() {
    cout << setprecision(15) << fixed;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}