← 返回题目列表

AtCoder · jsc2023_final_d

D. 两个异或

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

配点 : 900 点

問題文

长度 N 的非负整数序列 A=(A_1,A_2,\cdots,A_N) 。

您可以执行以下操作高々 2 回你可以。 此外,\oplus 以位为单位 \mathrm{XOR} 代表一个操作。 自由选择

  • 非負整数 X 。 然后每个 i=1,2,\cdots,N , 保持A_i 的值不变或 替换为 A_i \oplus X 。

操作后 求 A 元素的最小可能最大值。

位单位 \mathrm{XOR} 什么是操作?

非負整数 A, B 按位 \mathrm{XOR} 、A \oplus B 定义如下。

  • A \oplus B 二进制表示法 2^k (k \geq 0) 的位数是A, B 二进制表示法 2^k 数字中只有一位是 如果 1 如果 1,否则 0 。
例如,3 \oplus 5 = 6 (二进制表示法: 011 \oplus 101 = 110)。
一般情况 k 非负整数 p_1, p_2, p_3, \dots, p_k 按位 \mathrm{XOR} 满足 (\dots ((p_1 \oplus p_2) \oplus p_3) \oplus \dots \oplus p_k) ,即 可以证明 p_1, p_2, p_3, \dots, p_k 不依赖于顺序。

制約

  • 1 \leq N \leq 2^{18}
  • 0 \leq A_i < 2^{18}
  • 所有输入值均为整数。

入力

输入是按以下格式从标准输入给出的。

N
A_1 A_2 \cdots A_N

出力

打印答案。


入力例 1

4
0 1 2 3

出力例 1

0

例如,以下操作是可能的。 选择

  • X=1 。
    • i=2 , 保持A_2 的值 1 \oplus 1=0 。
    • i=4 , 保持A_4 的值 3 \oplus 1=2 。
  • X=2 。
    • i=3 , 保持A_3 的值 2 \oplus 2=0 。
    • i=4 , 保持A_4 的值 2 \oplus 2=0 。

此时,运行后 A 元素的最大值为 它变成 0 。 这显然是可实现的最小值,所以答案是 0 。


入力例 2

3
1 4 10

出力例 2

1

入力例 3

5
2023 2023 2023 2023 2023

出力例 3

0

入力例 4

27
206264 140501 79 66028 206233 140291 206082 140347 65912 140301 65824 140404 65851 65986 140497 140526 206162 140513 66031 206294 206085 186 206157 66019 140407 65923 65806

出力例 4

192