問題一覧 > 通常問題

No.1082 XORのXOR

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 348
作問者 : tyawanmusityawanmusi / テスター : CleyLCleyL
28 ProblemId : 3823 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2020-05-22 18:09:22

問題文

要素数$N$の非負整数列$A$があります。$A$の$i(1 \le i \le N)$番目の要素は$A_i$です。
茶碗蒸しくんは、次の操作を行います。

  • $A$を自由に並び替える。
  • $B_j = A_j \oplus A_{j+1} (1 \le j \le N-1)$である非負整数列$B$を作る。
  • $X = B_1 \oplus B_2 \oplus B_3 \oplus \dots \oplus B_{N-1}$を求める。
$X$の最大値を求めてください。
ただし、$\oplus$はビットXORの記号を表します。

※XORがわからない方はこちらのページを参照してください。
https://ja.wikipedia.org/wiki/%E6%8E%92%E4%BB%96%E7%9A%84%E8%AB%96%E7%90%86%E5%92%8C

制約

  • $2 \le N \le 2 \times 10^3$
  • $0 \le A_i \le 10^9$
  • $N, A_i$は整数

入力

$N$
$A_1\ A_2\ \dots\ A_N$

$1$行目には整数$N$が入力されます。
$2$行目には非負整数列$A$が空白区切りで入力されます。

出力

$X$の最大値を1行に出力してください。
最後に改行してください。

サンプル

サンプル1
入力
3
11 13 17
出力
28

$A$の並び替え方としては、$(11,13,17),(11,17,13),(13,11,17),(13,17,11),(17,11,13),(17,13,11)$があります。
このうち、$A$が$(13,11,17)$のときに$B$は$(6,26)$となり、$X=28$となります。これが$X$の最大値です。
また、$A$が$(17,11,13)$のときにも$X=28$となります。

サンプル2
入力
5
1 1 1 1 1
出力
0

どのように$A$を並び替えても$X=0$となります。

サンプル3
入力
8
47 36 12 71 79 85 81 74
出力
126

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。