Codeforces 923 C. Perfect Security

http://codeforces.com/contest/923/problem/C

 

Trie树

#include<cstdio>
#include<iostream>
using namespace std;
#define N 300001
#define M 30
int tot=1,tr[N*M][2],sum[N*M];
int a[N];
void read(int &x)
{
x=0; char c=getchar();
while(!isdigit(c)) c=getchar();
while(isdigit(c)) { x=x*10+c-'0'; c=getchar(); }
}
void insert(int x)
{
int now=1;
sum[now]++;
for(int i=M-1;i>=0;--i)
{
if(!tr[now][x>>i&1]) tr[now][x>>i&1]=++tot;
now=tr[now][x>>i&1];
sum[now]++;
}
}
int find(int x)
{
int now=1,y=0;
sum[now]--;
for(int i=M-1;i>=0;--i)
{
if(sum[tr[now][x>>i&1]]) now=tr[now][x>>i&1];
else now=tr[now][!(x>>i&1)],y+=1<<i;
sum[now]--;
}
return y;
}
int main()
{
int n,x;
read(n);
for(int i=1;i<=n;++i) read(a[i]);
for(int i=1;i<=n;++i)
{
read(x);
insert(x);
}
for(int i=1;i<=n;++i) printf("%d ",find(a[i]));
return 0;
}