#P18103. Game Show: XOR Edition
Game Show: XOR Edition
Game Show: XOR Edition
著名游戏节目又推出了新一季——这次是异或版!
参赛者有一个起初为空的袋子。接下来依次进行 轮。每轮给出一个从 中独立、均匀随机选出的整数,参赛者可以将它放入袋子,也可以永久放弃它。所有轮次结束后,奖金等于袋中所有数的异或和。空袋子的异或和视为 。
参赛者知道 ,也知道这些数的随机分布,但事先不知道具体数值。他会采用使奖金期望最大化的最优策略。如果在最优策略中,取或不取当前数字带来的期望相同,他总会选择取走它。
你是节目的制作人,已经拿到了明天会出现的整数列表;这些数确实是独立均匀随机生成的。为了节省奖金,你可以秘密改变它们出现的顺序,但不能改变数字本身。参赛者不知道你做了这件事,因此仍会采用上述策略。
请找出一种排列,使参赛者最终获得的奖金尽可能少。
输入格式
第一行包含两个整数 ,满足
这里 表示 。
第二行包含 个整数 ,满足 。保证它们是独立均匀随机生成的。
原题设置90个测试点:对每个 ,有6个测试点,其 从 到 按等差数列分布,包括两个端点。
输入只有一组数据。
输出格式
输出 个整数,即原数组的一种排列,使参赛者最终奖金最小。如果有多种最优排列,输出任意一种。
每个数的出现次数必须与输入一致。
样例输入
4 40
4 12 3 5 9 7 0 6 13 10
12 14 14 7 2 8 3 4 2 3
4 9 13 4 13 6 10 2 0 10
4 9 15 13 10 8 6 7 14 3
原题刻意不提供样例输出,原页的 *** 只是隐藏输出的标记,不是需要输出的内容。样例输入为了排版而增加了换行,实际读入时按空白分隔即可。