No.1082 XORのXOR
レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 356
作問者 :
tyawanmusi
/ テスター :
👑 
CleyL
タグ : / 解いたユーザー数 356
作問者 :
tyawanmusi
/ テスター :
👑 CleyL
問題文最終更新日: 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}$を求める。
ただし、$\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もしくは右上の雲マークをクリックしてアカウントを作成してください。