E - Adjacent Xor Game Editorial /

Time Limit: 5 sec / Memory Limit: 1024 MB

配点 : 2500 点

問題文

N 個の非負整数 A_1,A_2,\cdots,A_N が与えられます． 各 k=1,2,\cdots,N について，以下の問題を解いてください．

Alice と Bob が以下のようなゲームをします．

  • Alice が A_1,A_2,\cdots,A_N の中から k 個の数を選ぶ． 選んだ数を x_1,x_2,\cdots,x_k (順不同)とおく．

  • Bob が長さ 2k の非負整数列 y=(y_1,y_2,\cdots,y_{2k}) を作る． ここで，y は以下の条件を満たす必要がある．

    • 0 \leq y_1 \leq y_2 \leq \cdots \leq y_{2k}
    • z_i=y_{2i-1} \oplus y_{2i} と定義する． このとき，\{z_1,z_2,\cdots,z_k\} は多重集合として \{x_1,x_2,\cdots,x_k\} と一致する．

なお，\oplus はビット単位 \mathrm{XOR} 演算を表します．

このゲームのスコアを y_{2k} の値とします． Bob はスコアを最小化するように行動します． その上で Alice はスコアを最大化するように行動します． このとき，スコアはいくつになるでしょうか？

ビット単位 \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 250000
  • 1 \leq A_i \leq 10^9
  • 入力される値はすべて整数．

入力

入力は以下の形式で標準入力から与えられる．

N
A_1 A_2 \cdots A_N

出力

答えを出力せよ．

入力例 1

3
1 2 3

出力例 1

2
6
6

k=1 の場合を考えます．

  • Alice が x_1=1 を選んだ場合: Bob は y=(0,1) を作り，スコアは 1 になります．
  • Alice が x_1=2 を選んだ場合: Bob は y=(0,2) を作り，スコアは 2 になります．
  • Alice が x_1=3 を選んだ場合: Bob は y=(1,2) を作り，スコアは 2 になります．

よって Alice は x_1=2 または x_1=3 を選び， スコアは 2 になります．

k=2 の場合を考えます． Alice が (x_1,x_2)=(2,3) を選び，Bob が y=(1,2,4,6) を作ると，スコアは 6 になります． これは両者の最適な行動の一例であり，求める答えは 6 です．

k=3 の場合を考えます． Alice が (x_1,x_2,x_3)=(1,2,3) を選び，Bob が y=(0,1,1,2,4,6) を作ると，スコアは 6 になります． これは両者の最適な行動の一例であり，求める答えは 6 です．

入力例 2

5
1 1 1 1 1

出力例 2

1
3
5
7
9

入力例 3

5
1 2 4 8 16

出力例 3

16
24
28
30
31

入力例 4

20
167660508 377125547 866003430 419036363 234113368 201296307 408194538 249252693 207212853 190504619 306027011 652875643 335898069 545795899 204268068 274532279 342039277 975300308 901270584 360957186

出力例 4

536870912
1610612736
2684354560
3758096384
4831838208
4831838208
4831838208
4831838208
4831838208
5100273664
5100273664
5100273664
5100273664
5100273664
5100273664
5100273664
5100273664
5100273664
5100273664
5100273664

Score : 2500 points

Problem Statement

You are given N non-negative integers A_1,A_2,\cdots,A_N. For each k=1,2,\cdots,N, solve the following problem.

Alice and Bob play the following game.

  • Alice chooses k numbers from A_1,A_2,\cdots,A_N. Let x_1,x_2,\cdots,x_k be the chosen numbers (in arbitrary order).

  • Bob makes a sequence of 2k non-negative integers y=(y_1,y_2,\cdots,y_{2k}), which must satisfy the following conditions.

    • 0 \leq y_1 \leq y_2 \leq \cdots \leq y_{2k}.
    • Let z_i=y_{2i-1} \oplus y_{2i}. Then, \{z_1,z_2,\cdots,z_k\} coincides with \{x_1,x_2,\cdots,x_k\} as a multiset.

Here, \oplus denotes bitwise \mathrm{XOR}.

Let the score of the game be the value of y_{2k}. Bob plays to minimize the score. With this in mind, Alice plays to maximize the score. What will the score be?

What is bitwise \mathrm{XOR}?

The bitwise \mathrm{XOR} of non-negative integers A and B, A\ \mathrm{XOR}\ B, is defined as follows.

  • When A\ \mathrm{XOR}\ B is written in binary, the k-th lowest bit (k \geq 0) is 1 if exactly one of the k-th lowest bits of A and B is 1, and 0 otherwise.
For instance, 3\ \mathrm{XOR}\ 5 = 6 (in binary: 011\ \mathrm{XOR}\ 101 = 110).
Generally, the bitwise \mathrm{XOR} of k non-negative integers p_1, p_2, p_3, \dots, p_k is defined to be (\dots ((p_1\ \mathrm{XOR}\ p_2)\ \mathrm{XOR}\ p_3)\ \mathrm{XOR}\ \dots\ \mathrm{XOR}\ p_k), which one can prove to be independent of the order of p_1, p_2, p_3, \dots p_k.

Constraints

  • 1 \leq N \leq 250000
  • 1 \leq A_i \leq 10^9
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N
A_1 A_2 \cdots A_N

Output

Print the answer.

Sample Input 1

3
1 2 3

Sample Output 1

2
6
6

Consider the case k=1.

  • If Alice chooses x_1=1: Bob makes y=(0,1), for the score of 1.
  • If Alice chooses x_1=2: Bob makes y=(0,2), for the score of 2.
  • If Alice chooses x_1=3: Bob makes y=(1,2), for the score of 2.

Thus, Alice will choose x_1=2 or x_1=3, for the score of 2.

Consider the case k=2. If Alice chooses (x_1,x_2)=(2,3) and Bob makes y=(1,2,4,6), the score will be 6. This is an example of optimal play for both players, and the answer is 6.

Consider the case k=3. If Alice chooses (x_1,x_2,x_3)=(1,2,3) and Bob makes y=(0,1,1,2,4,6), the score will be 6. This is an example of optimal play for both players, and the answer is 6.

Sample Input 2

5
1 1 1 1 1

Sample Output 2

1
3
5
7
9

Sample Input 3

5
1 2 4 8 16

Sample Output 3

16
24
28
30
31

Sample Input 4

20
167660508 377125547 866003430 419036363 234113368 201296307 408194538 249252693 207212853 190504619 306027011 652875643 335898069 545795899 204268068 274532279 342039277 975300308 901270584 360957186

Sample Output 4

536870912
1610612736
2684354560
3758096384
4831838208
4831838208
4831838208
4831838208
4831838208
5100273664
5100273664
5100273664
5100273664
5100273664
5100273664
5100273664
5100273664
5100273664
5100273664
5100273664