Codeforces 1088D - Ehab and another another xor problem - 交互题

in 题解思维 with 0 comment

Codeforces 1088D - Ehab and another another xor problem

题解链接

https://lucien.ink


题目链接

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


题目

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:

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 \le a,b<2^{30}$.


题意

  对方隐藏了两个数$a$、$b$,你可以做一次询问? c d,对方会返回cmp(a ^ c, b ^ c)的值,要你在62步之内询问出$a$、$b$的值是多少。


思路

  总共有$30$位,给了$62$次机会,显然要逐个二进制搞一搞。对于最高位的二进制来说,不难发现,我们query一下1 0query一下0 1的返回值会很有意思:

  1. 如果当前最高位同为1,那么两次query的返回值一定为-11
  2. 如果当前最高位同为0,那么两次query的返回值一定为1-1
  3. 如果当前最高位不同,那么两次query的返回值一定相同。

  对于第三种情况看起来似乎有点难办?其实只要在最开始query一下0 0,根据返回值即可判断两个数的大小,那么最高位不同的时候大的那个数的最高位一定是1,另一个数则一定是0。随后更新一下两个数的大小关系即可。

  对于如何取最高位的问题,其实我们只要把前面已经得到的部分二进制和原数query一下,那么比当前位高的二进制位就自然变为0了。


实现

https://pasteme.cn/2210

#include <bits/stdc++.h>
int query(int a, int b, int ret = 0) {
    printf("? %d %d\n", a, b);
    fflush(stdout);
    scanf("%d", &ret);
    return ret;
}
int main() {
    int a = 0, b = 0;
    bool aIsBigger = true;
    if (query(a, b) < 0) aIsBigger = false;
    for (int i = 29; ~i; i--) {
        int x = query(a ^ (1 << i), b), y = query(a, b ^ (1 << i));
        if (x == y) {
            if (aIsBigger) a ^= (1 << i);
            else b ^= (1 << i);
            aIsBigger = (x == 1);
        } else if (x == -1 && y == 1) a ^= (1 << i), b ^= (1 << i);
    }
    printf("! %d %d\n", a, b);
    return 0;
}
Responses