/ 
Time Limit: 5 sec / Memory Limit: 1024 MB
配点 : 625 点
問題文
長さ 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 を二進表記した際の 2^k の位の数のうち一方のみが 1 であれば 1、そうでなければ 0 である。
また、長さ L の数列 B に対して B の中央値とは、B を昇順にソートして得られる数列を B' として B' の \lfloor \frac{L}{2} \rfloor + 1 番目の値のことを指します。
制約
- 1 \leq N \leq 10^5
- 0 \leq A_i < 2^{30}
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N
A_1 A_2 \ldots A_{2N}
出力
答えを出力せよ。
入力例 1
4 4 0 0 11 2 7 9 5
出力例 1
14
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_1 \oplus A_2, A_3 \oplus A_4, A_5 \oplus A_6, A_7 \oplus A_8) の中央値が 15 以上となるように A を並べ替えることは不可能であるため、14 を出力します。
入力例 2
1 998244353 1000000007
出力例 2
1755654
入力例 3
5 1 2 4 8 16 32 64 128 256 512
出力例 3
192
Score : 625 points
Problem Statement
You are given a sequence of length 2N: A = (A_1, A_2, \ldots, A_{2N}).
Find the maximum value that can be obtained as the median of the length-N sequence (A_1 \oplus A_2, A_3 \oplus A_4, \ldots, A_{2N-1} \oplus A_{2N}) by rearranging the elements of the sequence A.
Here, \oplus represents bitwise exclusive OR.
What is bitwise exclusive OR?
The bitwise exclusive OR of non-negative integers A and B, denoted as A \oplus B, is defined as follows:- The number at the 2^k position (k \geq 0) in the binary representation of A \oplus B is 1 if and only if exactly one of the numbers at the 2^k position in the binary representation of A and B is 1, and it is 0 otherwise.
Also, for a sequence B of length L, the median of B is the value at the \lfloor \frac{L}{2} \rfloor + 1-th position of the sequence B' obtained by sorting B in ascending order.
Constraints
- 1 \leq N \leq 10^5
- 0 \leq A_i < 2^{30}
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N
A_1 A_2 \ldots A_{2N}
Output
Print the answer.
Sample Input 1
4 4 0 0 11 2 7 9 5
Sample Output 1
14
By rearranging A as (5, 0, 9, 7, 11, 4, 0, 2), we get (A_1 \oplus A_2, A_3 \oplus A_4, A_5 \oplus A_6, A_7 \oplus A_8) = (5, 14, 15, 2), and the median of this sequence is 14.
It is impossible to rearrange A so that the median of (A_1 \oplus A_2, A_3 \oplus A_4, A_5 \oplus A_6, A_7 \oplus A_8) is 15 or greater, so we print 14.
Sample Input 2
1 998244353 1000000007
Sample Output 2
1755654
Sample Input 3
5 1 2 4 8 16 32 64 128 256 512
Sample Output 3
192