如果你说阿尔卡迪下跳棋有点老派,那你就错了。还有阿尔卡迪和他的朋友们热衷的现代电脑游戏。我们不会讨论它的规则,对于这个问题唯一重要的特征是每个玩家必须在游戏开始时选择一个不同的英雄。
有 $$$2$$$ 团队,每个团队都有 $$$n$$$ 玩家和 $$$2n$$$ 英雄在团队之间分配。各队轮流选择英雄:首先,第一队选择本队英雄,然后第二队选择英雄,以此类推。请注意,选择英雄后,两队都将无法使用该英雄。
朋友们估计第$$$i$$$英雄的力量为$$$p_i$$$。每个团队都希望最大化其英雄的总力量。然而,有一个例外:有 $$$m$$$ 的英雄对彼此特别强大,因此当任何一支队伍从这样的一对英雄中选择一个英雄时,另一支队伍必须在轮到时选择另一个英雄。每个英雄最多属于这样的一对。
这是一个交互问题。您将编写一个程序,为一支球队最佳选择英雄,而陪审团的程序将为另一支球队比赛。请注意,陪审团的程序可能会表现得很低效,在这种情况下,您必须抓住机会,并仍然最大限度地发挥您团队的总力量。正式来说,如果您有机会达到 $$$q$$$ 或更高的总功率,无论陪审团的程序选择如何,您都必须获得 $$$q$$$ 或更高才能通过测试。
输入
第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n \le 10^3$$$, $$$0 \le m \le n$$$)——一支队伍中的玩家数量和特殊英雄对的数量。
第二行包含 $$$2n$$$ 整数 $$$p_1, p_2, \ldots, p_{2n}$$$ ($$$1 \le p_i \le 10^3$$$) — 英雄的力量。
接下来的 $$$m$$$ 行包含两个整数 $$$a$$$ 和 $$$b$$$ ($$$1 \le a, b \le 2n$$$, $$$a \ne b$$$) - 一对彼此特别强大的英雄。保证每个英雄在此列表中最多出现一次。
下一行包含一个整数 $$$t$$$ ($$$1 \le t \le 2$$$) — 您要效力的球队。如果$$$t = 1$$$,则第一轮是你的,否则你有第二轮。
黑客
为了破解,请使用上述格式并附加一行。在此行中,输出从 $$$1$$$ 到 $$$2n$$$ 的不同整数 $$$2n$$$ — 陪审团团队的优先顺序。评审团团队将在每个回合中从此列表中选择第一个可能的英雄。这里可能的意思是尚未被采用,并且与特殊英雄对的规则不矛盾。
互动
轮到你时,打印一个整数 $$$x$$$ ($$$1 \le x \le 2n$$$) - 你选择的英雄的索引。请注意,您不能选择您或其他玩家之前选择的英雄,并且必须遵循特殊英雄对的规则。
当轮到对方队伍时,读取包含单个整数 $$$x$$$ ($$$1 \le x \le 2n$$$) 的行——对方选择的英雄的索引。保证这个指标之前没有被选择过,并且对方也遵循特殊英雄对的规则。
最后一轮结束后,您应该终止而不打印任何内容。
打印您的选择后,不要忘记输出行尾并刷新输出。否则您将超出空闲限制。为此,请使用:
- C++ 中的 fflush(stdout) 或 cout.flush();
- Java 中的 System.out.flush();
- 帕斯卡刷新(输出);
- Python 中的 stdout.flush() ;
- 请参阅其他语言的文档。
陪审团的答案 $$$-1$$$ 而不是有效的选择,意味着你做出了无效的回合。收到$$$-1$$$后立即退出,您将看到错误的答案判决。否则,您可以获得任意判决,因为您的解决方案将继续从关闭的流中读取。
示例
输入 #1
3 1 1 2 3 4 5 6 2 6 1 2 4 1
输出 #1
6 5 3
输入 #2
3 1 1 2 3 4 5 6 1 5 2 6 1 3
输出 #2
5 4 2
注意
在第一个示例中,第一个回合是你的。例如,您选择$$$6$$$,另一队被迫回复$$$2$$$。您选择$$$5$$$,其他团队选择$$$4$$$。最后,你选择$$$3$$$,另一队选择$$$1$$$。
在第二个例子中,你有第二个回合。另一队选择$$$6$$$,你选择$$$5$$$,迫使另一队选择$$$1$$$。现在您选择$$$4$$$,其他团队选择$$$3$$$,您选择$$$2$$$。