No.5001 Running with Exclusive OR
タグ : / 解いたユーザー数 54
作問者 :
yuki2006
Note
This problem was created as a pilot for testing the functionality of score-based problems, and an optimal solution may exist.It may not be interesting as a score-based problem. It may have appeared before.
As the problem setter, I will not provide an editorial. (Or rather, unfortunately, I cannot.)
Since this is a pilot version, various things may change.
You may submit once every 5 minutes.
Please refrain from repeatedly submitting simple randomized solutions.
The problem is scheduled to end on 2018-03-23 22:00:00.
Although it runs for one week, this does not mean I want you to work on it intensively.
You are welcome to tweet hints.
You can still submit after the problem ends.
Problem Statement
You are given an integer sequence $A$ of $N$ distinct elements, each of which is at least 1.
Choose $M$ of them without duplication so that the value obtained by applying the exclusive OR (XOR) operation to all the chosen elements is as large as possible.
That is, $A_{k_1} \oplus A_{k_2} \oplus \cdots \oplus A_{k_M}$ ($\oplus$ denotes exclusive OR).
This value is the score, and the sum of the scores over all cases is the score of the submission.
Input
$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 $
The values are generated simply at random within the constraints. The judge data does not include the sample cases below.
Output
$A_{k_1}\ A_{k_2}\ \cdots\ A_{k_M} $
Print a newline at the end.
Note that you should output the values, not the indices.
Sample
Sample 1
Input
5 3 1 5 3 4 2
Output
1 2 4
$1 \oplus 2 \oplus 4$
gives the maximum value, 7.
Sample 2
Input
5 2 1 3 4 2 5
Output
2 1
You can get AC even if the value is not the best, but your score will not necessarily be high. The elements may be output in any order.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。