$$Doubt$$

$最初想法$

按顺序构造 $c_i$, 每次 贪心 地将 $\min (a⨁b)$ 取出, 作为 $c_i$, 可以保证字典序最小,
朴素实现是 $O(N^2)$ 的, 加上用 桶 对第二个测试点 相同的数字加速处理 可以获得 $50pts$ .

考虑直接找每个 $a_i$ 所匹配的 $b_i$, 发现若 $a_i$ 找了 $b_i$, 会影响到后面的 $a_j$ 找 $b_i$, 换句话说, 这样会有后效性 .

$正解部分$

不用关心 $a_i$ 匹配哪个 $b_i$, 只需使得 $c$ 的 较小值较小 即可实现 字典序最小,

于是对 $a$ 和 $b$ 分别开一个 深度越大, 位数越低 的 $0/1Trie$树,
从两颗 $Trie$树 贪心 地从根节点同步向下走, 优先走权值相同的节点, 使得 $c$ 的 越小值越小 即可 .

$实现部分$

• 根节点的下标赋为 $1$, $0$ 节点留作 虚点, 用来判边界 .
• $Trie$ 中的 $Add()$ 函数, $to$ 要开 $bool$ 类型 .

#include<bits/stdc++.h>
#define reg registerint read(){char c;int s = 0, flag = 1;while((c=getchar()) && !isdigit(c))if(c == '-'){ flag = -1, c = getchar(); break ; }while(isdigit(c)) s = s*10 + c-'0', c = getchar();return s * flag;
}const int maxn = 6e6 + 10;struct Trie{int rot;int node_cnt;struct Node{ int ch[2], cnt; } T[maxn];void Add(int x){int cur = rot;for(reg int i = 30; i >= 0; i --){bool to = (x & (1 << i));if(!T[cur].ch[to]) T[cur].ch[to] = ++ node_cnt;cur = T[cur].ch[to];T[cur].cnt ++;}}} t_a, t_b;int c_cnt;
int c[maxn];void DFS(int k_1, int k_2, int sum, int pw){if(k_1) t_a.T[k_1].cnt --, t_b.T[k_2].cnt --;if(pw == 0){ c[++ c_cnt] = sum; return ; }while(t_a.T[t_a.T[k_1].ch[0]].cnt && t_b.T[t_b.T[k_2].ch[0]].cnt) DFS(t_a.T[k_1].ch[0], t_b.T[k_2].ch[0], sum, pw>>1);while(t_a.T[t_a.T[k_1].ch[1]].cnt && t_b.T[t_b.T[k_2].ch[1]].cnt) DFS(t_a.T[k_1].ch[1], t_b.T[k_2].ch[1], sum, pw>>1);while(t_a.T[t_a.T[k_1].ch[1]].cnt && t_b.T[t_b.T[k_2].ch[0]].cnt) DFS(t_a.T[k_1].ch[1], t_b.T[k_2].ch[0], sum|pw, pw>>1);while(t_a.T[t_a.T[k_1].ch[0]].cnt && t_b.T[t_b.T[k_2].ch[1]].cnt) DFS(t_a.T[k_1].ch[0], t_b.T[k_2].ch[1], sum|pw, pw>>1);
}int N;int main(){N = read();t_a.rot = t_b.rot = 1;t_a.node_cnt = t_b.node_cnt = 1;for(reg int i = 1; i <= N; i ++) t_a.Add(read());for(reg int i = 1; i <= N; i ++) t_b.Add(read());DFS(1, 1, 0, 1<<30);std::sort(c+1, c+c_cnt+1);for(reg int i = 1; i <= c_cnt; i ++) printf("%d ", c[i]);return 0;
}