/ 
実行時間制限: 4 sec / メモリ制限: 1024 MB
配点 : 700 点
問題文
黒板に 2N 個の整数が書かれており，そのうち i 番目の整数は A_i です．
Alice と Bob がゲームをします． ゲームは N ラウンドにわたって行われ，各ラウンドでは以下の操作を行います．
-
まず，Alice が黒板に書かれている整数を一つ選び，消す． ここで選ばれた整数を x とする．
-
次に，Bob が黒板に書かれている整数を一つ選び，消す． ここで選ばれた整数を y とする．
-
x \oplus y の値をノートに記録する．ただしここで \oplus はビットごとの排他的論理和を表す．
最終的に，黒板からは全ての整数が消え去り，ノートには N 個の整数が記録されます． ゲームのスコアは，ノートに記録された整数の最大値です． Alice の目標はスコアを最大化することで，Bob の目標はスコアを最小化することです． 両者が最適に行動した場合，ゲームのスコアがいくつになるか求めてください．
制約
- 1 \leq N \leq 2 \times 10^5
- 0 \leq A_i < 2^{30}
- 入力される値はすべて整数である
入力
入力は以下の形式で標準入力から与えられる．
N
A_1 A_2 \cdots A_{2N}
出力
答えを出力せよ．
入力例 1
2 0 1 3 5
出力例 1
4
例えば，以下のようなゲームの進行が考えられます．なお，この進行が最適な手順であるとは限りません．
-
ラウンド 1:
- Alice が A_1=0 を選択する．
- Bob が A_3=3 を選択する．
- ノートに 0 \oplus 3=3 が記録される．
-
ラウンド 2:
- Alice が A_4=5 を選択する．
- Bob が A_2=1 を選択する．
- ノートに 5 \oplus 1=4 が記録される．
-
ゲームのスコアが \max(3,4)=4 になる．
入力例 2
2 0 0 0 0
出力例 2
0
入力例 3
10 974654030 99760550 750234695 255777344 907989127 917878091 818948631 690392797 579845317 549202360 511962375 203530861 491981716 64663831 561104719 541423175 301832976 252317904 471905694 350223945
出力例 3
268507123
Score : 700 points
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