問題一覧 > スコア問題

No.5001 排他的論理和でランニング

レベル : / 実行時間制限 : 1ケース 1.500秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 （複数の解が存在する可能性があります）
タグ : / 解いたユーザー数 53
作問者 : yuki2006yuki2006
0 ProblemId : 1390 / 自分の提出
問題文最終更新日: 2018-06-02 15:17:49

Note

この問題は、スコア形式の問題の機能テストのパイロット版として作られた問題で、最適解があるかもしれません。
スコア形式の問題として面白くないかもしれません。既出かもしれません。
作問者としては、解説を用意しません。（というか残念ながらできません。）
パイロット版なのでいろいろ変わるかもしれません。

提出は5分に1度ごとです。
単純な乱択解を何度も投げるのはご遠慮ください。
出題終了は2018-03-23 22:00:00の予定です。
1週間だからといって、ガッツリやってほしいわけではありません。
ヒントをツイートするのはかまいません。
出題終了時の後にも、提出することができます。

問題文

$N$個の重複なしの、各要素が1以上の整数列$A$が与えられます。　

そこから、重複せずに$M$個選んで、すべての選んだものに対して排他的論理和（XOR）演算を行ったときの値がなるべく大きくなる組み合わせを選んでください。
つまり、$A_{k_1} \oplus A_{k_2} \oplus \cdots \oplus A_{k_M}$ ($\oplus$は排他的論理和である。)

この値をスコアとし、各ケースのスコアの合計が提出のスコアとなる。

入力

$N\ M$
$A_1 \ A_2 \ ... A_N$

$ 5 \le N \le 10^5$
$1 \le M \le N$
$ 1 \le A_i \le 10^6$
$ A_i \ne A_j $

制約内の値を単純に乱数で生成しております。ジャッジには下記のサンプルケースは含まれておりません。

出力

$A_{k_1}\ A_{k_2}\ \cdots\ A_{k_M} $

最後に改行をしてください。
インデックスではないことに気をつけてください。

サンプル

サンプル1
入力
5 3
1 5 3 4 2
出力
1 2 4

$1 \oplus 2 \oplus 4$
が最大の 7 になります。

サンプル2
入力
5 2
1 3 4 2 5
出力
2 1

最良値ではなくてもACはでるが、スコアが高いとは限らない。出力する順番はばらばらでも構わない。

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