比赛 26暑假集训模拟赛1 评测结果 AAAAAAAAAA
题目名称 异或加密 最终得分 100
用户昵称 zcx 运行时间 1.680 s
代码语言 C++ 内存使用 9.21 MiB
提交时间 2026-06-29 09:45:54
显示代码纯文本
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e6 + 5;

int n,key = 0;

int a[N],b[N];

void dfs(int l1,int r1,int l2,int r2,int x){
    int l = l1,r = r1,num1,num2;
    while(l < r){
        int mid = (l + r + 1)>>1;
        if(a[mid] & (1<<x)) l = mid;
        else r = mid - 1;
    }
    num1 = l - l1 + 1;
    if(!(a[l] & (1<<x))) num1 = 0;
    l = l2,r = r2;
    while(l < r){
        int mid = (l + r + 1)>>1;
        if(b[mid] & (1<<x)) l = mid;
        else r = mid - 1;
    }
    num2 = l - l2 + 1;
    if(!(b[l] & (1<<x))) num2 = 0;
    if(num1 == num2){
        if(!x) return;
        if(num1 & 1){
            dfs(l1,l1 + num1 - 1,l2,l2 + num2 - 1,x - 1);
        }else dfs(l1 + num1,r1,l2 + num2,r2,x - 1);
    }else{
        key += (1<<x);
        if(!x) return;
        if(num1 & 1){
            dfs(l1,l1 + num1 - 1,l2 + num2,r2,x - 1);
        }else dfs(l1 + num1,r1,l2,l2 + num2 - 1,x - 1);
    }
}

bool cmp(int x,int y){
    return x > y;
}

signed main()
{
    freopen("XORcipher.in","r",stdin);
    freopen("XORcipher.out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>n;
    for(int i = 1;i <= n;i++) cin>>a[i];
    for(int i = 1;i <= n;i++) cin>>b[i];
    sort(a + 1,a + 1 + n,cmp);
    sort(b + 1,b + 1 + n,cmp);
    dfs(1,n,1,n,30);
    cout<<key<<endl;
    return 0;
}