Codeforces 923 C. Perfect Security

116 阅读 0 评论 77 点赞

我是靠谱客的博主腼腆橘子，这篇文章主要介绍Codeforces 923 C. Perfect Security，现在分享给大家，希望可以做个参考。

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

Trie树

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#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;
}