这是一个交互问题。
考虑一个固定正整数$$$n$$$。两个玩家,第一和第二玩游戏如下:
1. 首先考虑 $$$2n$$$ 数字 $$$1, 2, \dots, 2n$$$,并根据需要将它们划分为 $$$n$$$ 不相交的对。
2. 然后,Second 从 First 创建的每一对中精确选择一个元素(他选择他想要的元素)。
为了确定游戏的获胜者,我们计算 Second 选择的数字的总和。如果所有这些数字的总和是 $$$2n$$$ 的倍数,则第二个获胜。否则,First 获胜。
给你整数 $$$n$$$。你的任务是决定你想扮演哪位玩家并赢得比赛。
互动
交互从读取整数 $$$n$$$ ($$$1 \le n \le 5 \cdot 10^5$$$) 开始。
阅读后,打印一行包含 First 或 Second 的行,表示您想扮演的角色。然后,互动会根据您选择扮演的角色而有所不同。
如果您选择扮演 First,则打印一行,其中包含 $$$2n$$$ 整数 $$$p_1, p_2, \dots, p_{2n}$$$,表示数字 $$$i$$$ 属于 $$$1\le i \le 2n$$$ 的第 $$$p_i$$$ 对。因此,$$$1 \le p_i \le n$$$ 以及 $$$1$$$ 和 $$$n$$$ 之间的每个数字都应该恰好出现两次。
如果您选择扮演第二个,交互器将打印 $$$2n$$$ 整数 $$$p_1, p_2, \dots, p_{2n}$$$,表示数字 $$$i$$$ 属于第 $$$p_i$$$ 对。作为响应,在一行中打印 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$。这些应该包含每对中的一个数字。
无论你选择扮演谁,交互者都将通过打印一个整数来完成:如果你对测试用例的答案正确,$$$0$$$(也就是说,你作为第一玩,它无法从你的配对中选择足够的数字,或者你作为第二玩,并且你选择的数字加起来是 $$$2n$$$ 的倍数),或者 $$$-1$$$ 如果不正确。特别是,如果您选择先玩并输了,交互器将不会打印所选的数字。无论哪种情况,您的程序都应在读取此数字后立即终止。
如果您在任何时候进行无效交互,交互器将打印 $$$-1$$$ 并完成交互。您将收到错误答案的判决。确保立即终止以避免得到其他判决。
打印后不要忘记输出行尾并刷新输出。否则,您将超出空闲限制。为此,请使用:
- C++ 中的 fflush(stdout) 或 cout.flush();
- Java 中的 System.out.flush();
- 帕斯卡刷新(输出);
- Python 中的 stdout.flush() ;
- 请参阅其他语言的文档。
黑客格式
要破解,请使用以下格式:
第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 5 \cdot 10^5$$$)。
第二行包含 $$$2n$$$ 整数 $$$p_1, p_2, \dots, p_{2n}$$$,表示如果被黑客攻击的解决方案选择扮演第二个,则数字 $$$i$$$ 属于第 $$$p_i$$$ 对。如果被黑客攻击的解决方案选择作为 First,这些对并不重要,但 $$$p_1, p_2, \dots, p_{2n}$$$ 仍然必须形成 $$$1, 2, \dots, 2n$$$ 到 $$$n$$$ 不相交对的有效分区。
示例
输入 #1
2 1 1 2 2 0
输出 #1
Second 1 3
输入 #2
2 0
输出 #2
First 2 1 2 1
注意
在第一个示例中,$$$n = 2$$$,并且您决定扮演第二名。法官选择 $$$(1, 2)$$$ 和 $$$(3, 4)$$$ 对,你用数字 $$$1$$$ 和 $$$3$$$ 回复。这是一个有效的选择,因为它只包含每一对中的一个数字,并且 $$$1 + 3 = 4$$$ 之和可被 $$$4$$$ 整除。
在第二个示例中,$$$n 再次 = 2$$$,并且您扮演 First。您选择 $$$(2, 4)$$$ 和 $$$(1, 3)$$$ 对。法官未能从每一对中选择一个数字,使其总和可被 $$$4$$$ 整除,因此答案是正确的。
请注意,示例测试仅用于说明交互协议,并不一定对应于真实交互器的行为。