Problem Statement
There are $2N$ integers written on a blackboard. The $i$-th integer is $A_i$.
Alice and Bob will play a game consisting of $N$ rounds. In each round, they do the following:
- First, Alice chooses an integer on the blackboard and erases it. Let $x$ be the integer erased here.
- Second, Bob chooses an integer on the blackboard and erases it. Let $y$ be the integer erased here.
- Finally, write the value $x \oplus y$ on a notebook, where $\oplus$ denotes the bitwise XOR.
In the end, all the integers on the blackboard will be erased, and the notebook will have $N$ integers written on it. The greatest integer written on the notebook will be the score of the game. Alice wants to maximize this score, while Bob wants to minimize it. Find the score of the game when both players play optimally under their objectives.
Constraints
- $1 \leq N \leq 2 \times 10^5$
- $0 \leq A_i < 2^{30}$
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
$N$
$A_1$ $A_2$ $\cdots$ $A_{2N}$
Output
Print the answer.
Sample Input 1
2 0 1 3 5
Sample Output 1
4
Below is one possible progress of the game (it may contain suboptimal choices).
-
Round $1$:
- Alice chooses $A_1=0$.
- Bob chooses $A_3=3$.
- They write $0 \oplus 3=3$ on the notebook.
-
Round $2$:
- Alice chooses $A_4=5$.
- Bob chooses $A_2=1$.
- They write $5 \oplus 1=4$ on the notebook.
-
The score of the game is $\max(3,4)=4$.
Sample Input 2
2 0 0 0 0
Sample Output 2
0
Sample Input 3
10 974654030 99760550 750234695 255777344 907989127 917878091 818948631 690392797 579845317 549202360 511962375 203530861 491981716 64663831 561104719 541423175 301832976 252317904 471905694 350223945
Sample Output 3
268507123
首先发现 Alice 是个废物，因为 Bob 找到原图一个匹配后， Alice 选什么 Bob 就选对应的那个即可。
所以现在要找到一个匹配，使得每条边两边的异或最大值最小。
考虑使用 trie 来分析。
对于某一个节点 \(x\) 的子树，如果他的左子树和右子树大小都是偶数，那么两个子树都可以自己完成匹配，可以递归到里面计算。
否则，就让他们自己匹配完之后，两个子树各自选出一个异或。所以可以递归计算两个子树中各选一个数异或的最小值。
#include<bits/stdc++.h>
using namespace std;
const int N=4e5+5;
int n,a[N],ret=0,tr[N*30][2],mx=-1,tg[N*30],idx,s[30],sz[N*30];
void insert(int x)
{
int u=0;
for(int i=29;~i;--i)
{
if(!tr[u][x>>i&1])
tr[u][x>>i&1]=++idx;
u=tr[u][x>>i&1];
sz[u]++;
}
tg[u]=x;
}
int ask(int x,int y)
{
if(!x||!y)
return INT_MAX;
if(tg[x])
return tg[x]^tg[y];
if(!tr[x][0]&&!tr[y][1])
return ask(tr[x][1],tr[y][0]);
if(!tr[x][1]&&!tr[y][0])
return ask(tr[x][0],tr[y][1]);
return min(ask(tr[x][0],tr[y][0]),ask(tr[x][1],tr[y][1]));
}
void solve(int x)
{
if(sz[tr[x][0]]&1)
ret=max(ret,ask(tr[x][0],tr[x][1]));
else
{
if(tr[x][0])
solve(tr[x][0]);
if(tr[x][1])
solve(tr[x][1]);
}
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n*2;i++)
{
scanf("%d",a+i);
for(int j=0;j<30;j++)
if(a[i]>>j&1)
s[j]++;
}
for(int i=1;i<=n*2;i++)
insert(a[i]);
solve(0);
printf("%d",ret);
}