AT_abc304_g [ABC304G] Max of Medians

题目描述

给定一个长度为 $2N$ 的数列 $A = (A_1, A_2, \ldots, A_{2N})$。

通过重新排列数列 $A$ 的元素，可以得到一个长度为 $N$ 的数列 $(A_1 \oplus A_2, A_3 \oplus A_4, \ldots, A_{2N-1} \oplus A_{2N})$。请你求出作为该数列的中位数所能取得的最大值。

这里，$\oplus$ 表示按位异或运算。

什么是按位异或运算？对于非负整数 $A, B$，它们的按位异或 $A \oplus B$ 定义如下：

• $A \oplus B$ 的二进制表示中，第 $2^k$ 位（$k \geq 0$）的数，如果 $A$ 和 $B$ 的二进制表示中该位只有一个为 $1$，则为 $1$，否则为 $0$。

例如，$3 \oplus 5 = 6$（二进制表示为：$011 \oplus 101 = 110$）。

另外，对于长度为 $L$ 的数列 $B$，$B$ 的中位数定义为：将 $B$ 按升序排序得到 $B'$，则 $B'$ 的第 $\lfloor \frac{L}{2} \rfloor + 1$ 个值即为中位数。

输入格式

输入以如下格式从标准输入读入。

$N$ $A_1$ $A_2$ $\ldots$ $A_{2N}$

输出格式

请输出答案。

输入输出样例 #1

输入 #1

4
4 0 0 11 2 7 9 5

输出 #1

14

输入输出样例 #2

输入 #2

1
998244353 1000000007

输出 #2

1755654

输入输出样例 #3

输入 #3

5
1 2 4 8 16 32 64 128 256 512

输出 #3

192

说明/提示

限制条件

• $1 \leq N \leq 10^5$
• $0 \leq A_i < 2^{30}$
• 输入均为整数

样例解释 1

将 $A$ 排列为 $(5, 0, 9, 7, 11, 4, 0, 2)$ 时，$(A_1 \oplus A_2, A_3 \oplus A_4, A_5 \oplus A_6, A_7 \oplus A_8) = (5, 14, 15, 2)$，该数列的中位数为 $14$。无法通过重新排列 $A$ 使得 $(A_1 \oplus A_2, A_3 \oplus A_4, A_5 \oplus A_6, A_7 \oplus A_8)$ 的中位数达到 $15$ 或更大，因此输出 $14$。

由 ChatGPT 4.1 翻译