CF2187B Shortest Statement Ever

题目描述

给定两个非负整数 x 和 y，请找出两个非负整数 p 和 q，使得 p\;\&\;q=0，并且 |x-p|+|y-q| 最小。这里，\& 表示按位与运算。

输入格式

输入包含多组测试用例。第一行为测试用例个数 t（1 \le t \le 10^4）。
接下来的每个测试用例占一行，每行包含两个非负整数 x 和 y（0 \le x, y < 2^{30}）。

输出格式

对于每组测试用例，输出一行两个非负整数 p 和 q，为你找到的一组满足条件的解。如果满足条件的 (p, q) 有多组合法解，你可以输出其中任意一组。

可以证明，在题目给定的约束下，任一组合法解都满足 \max(p, q) < 2^{31}。

输入输出样例 #1

输入 #1

7
0 0
1 1
3 6
7 11
4 4
123 321
1073741823 1073741822

输出 #1

0 0
2 1
3 8
6 9
4 3
128 321
1073741824 1073741822

说明/提示

对于第一个测试用例，一组合法解为 p=0，q=0，因为 0\,\&\,0=0，并且 |x-p|+|y-q|=|0-0|+|0-0|=0，在所有解中取到最小。

对于第三个测试用例，一组合法解为 p=3，q=8，因为 3\,\&\,8=0，并且 |x-p|+|y-q|=|3-3|+|8-6|=2。注意 (p, q)=(3, 4) 也是一组合法解。

代码

int get_best_x(int x,int y){  
    int p=31-__builtin_clz(x|1);  
        int big=x;  
        for(int i=p;i>=0;i--){  
        if((((x>>i)&1)&((y>>i)&1))){  
            for(int j=i+1;j<=31;j++){  
                if((((x>>j)&1)|((y>>j)&1))==0){  
                    big=((x>>j)<<j)+(1ll<<j);  
                    goto cat;  
                }  
            }  
        }  
    }  
        cat:;  
    int other=x;  
    bool flag=false;  
    for(int i=p;i>=0;i--){  
        if(!flag&&(((x>>i)&1)&((y>>i)&1))){  
            flag=true;  
            other&=~(1ll<<i);  
            continue;  
        }  
        if(flag){  
            if(((y>>i)&1)==0){  
                other|=(1ll<<i);  
            }else{  
                other&=~(1ll<<i);  
            }  
        }  
    }  
        if(abs(big-x)<abs(x-other)){  
        return big;  
    }else{  
        return other;  
    }  
}  
  
void solve() {  
    int x,y;  
    cin>>x>>y;  
        int best1=get_best_x(x,y);  
    int cost1=abs(best1-x);  
        int best2=get_best_x(y,x);  
    int cost2=abs(best2-y);  
        if(cost1<=cost2){  
        cout<<best1<<" "<<y<<endl;  
    }else{  
        cout<<x<<" "<<best2<<endl;  
    }  
}