← 返回题目列表

AtCoder · arc122_d

D. 异或游戏

中文机器翻译题面 查看原题

分数: 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:

    • 爱丽丝选择 A_1=0.
    • 鲍勃选择 A_3=3.
    • 他们写 0 \oplus 3=3 在笔记本上。
  • 圆形 2:

    • 爱丽丝选择 A_4=5.
    • 鲍勃选择 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