東京海上日動 プログラミングコンテスト2021 (AtCoder Regular Contest 122)
翻译中…
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.
翻译中…
样例
Input #1
2
0 1 3 5
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$.
Input #2
2
0 0 0 0
Output #2
0
Input #3
10
974654030 99760550 750234695 255777344 907989127 917878091 818948631 690392797 579845317 549202360 511962375 203530861 491981716 64663831 561104719 541423175 301832976 252317904 471905694 350223945
Output #3
268507123
题目信息
题面与样例版权归 AtCoder 及出题人所有;中文翻译由 AI 生成(CI 管线),如有出入请以原文为准。