这是一个交互问题。
数轴上有 $$$n$$$ 条蛇。第 $$$i$$$ 条蛇位于位置 $$$a_i$$$,速度为 $$$s_i$$$。您知道每条蛇的位置,并且每条蛇的速度是从 $$$0$$$ 到 $$$2$$$ 之间的整数,但您不知道每条蛇的确切速度。保证没有两条蛇处于同一位置。
要计算蛇的速度,您可以给出 高达 $$$3$$$ 说明。每条指令应以包含字母的长度 $$$m$$$ 的二进制字符串的形式给出 L 和 R ($$$1 \leq m \leq 4n$$$)。收到此指令后,蛇将移动 $$$m$$$ 秒。在第 $$$i$$$ 秒,如果 $$$s_i=$$$L,那么所有蛇在那一秒都向左移动。否则,所有蛇在那一秒都会向右移动。如果两条蛇在任意给定点位于同一位置(包括时间不是整数秒),则速度较快的蛇会从棋盘上移除。经过所有 $$$m$$$ 秒后,您将获得剩余蛇的数量以及所有剩余蛇的位置。请注意,每条指令都是相互独立的 - 这意味着所有蛇都会复活并移动到原来的位置。
你的任务是找出所有蛇的速度。然而,可能的情况是不可能找到至少一条蛇的速度。如果出现这种情况,您必须报告 -1 代替。你应该只输出 -1 如果无论给出哪种指令都无法计算出至少一条蛇的速度。 如果您举报 -1 当有一系列最多 $$$3$$$ 指令将唯一确定每条蛇的速度时,您将得到错误答案判决。 同样,如果您没有报告,您将收到错误答案判决 -1 当配置无法确定时,即使您正确猜测了速度。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^3$$$)。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ – 蛇的数量 ($$$2 \leq n \leq 10^5$$$)。
第二行包含 $$$n$$$ 整数 $$$a_1,a_2,\ldots,a_n$$$ ($$$1 \leq a_1 \lt a_2 \lt \ldots \lt a_n \leq 4n$$$) – 所有蛇的初始位置。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$10^5$$$。
互动
读取所有蛇的位置后,交互开始。要发出指令,请按以下格式输出一行:
- ? s
你应该保证 $$$s$$$ 仅包含字母 L 和 R,长度在 $$$1$$$ 和 $$$4n$$$ 之间(含)。
评审团将返回以下格式的一行:
- $$$k\:b_1\:b_2\:\ldots\:b_k\:(1 \leq k \leq n, -10^9 \leq b_1 \lt b_2 \lt \ldots \lt b_k \leq 10^9$$$)
这里,$$$k$$$ 是完整指令后剩余的蛇的数量,$$$b_1,b_2,\ldots,b_k$$$ 是它们的最终位置。
当你准备好输出答案时,按以下格式输出一行:
- 如果无法确定所有蛇的速度,则输出 ! -1
- 否则,输出 ! $$$s_1$$$ $$$s_2$$$ $$$\ldots$$$ $$$s_n$$$ ($$$0 \leq s_i \leq 2$$$)。这里,$$$s_i$$$ 应该表示输入中给出的第 $$$i$$$ 条蛇的速度。
打印答案不算作指示。
此后,继续下一个案例,如果这是最后一个测试案例,则终止程序。
交互器是 不 自适应。这意味着所有蛇的速度都是预先固定的,在交互过程中不会改变。进一步保证存在解——即所有蛇运动后的最终位置与其速度一致。
打印每个查询后,不要忘记输出行尾并刷新$$$^{\text{*}}$$$ 输出。否则,你会得到 超出空闲限制 判决。
如果在任何交互步骤中您读取 $$$-1$$$ 而不是有效数据,您的解决方案必须立即退出。这意味着您的解决方案将收到 错误答案 由于无效查询或任何其他错误。未能退出可能会导致任意判决,因为您的解决方案将继续从关闭的流中读取。
黑客
要进行破解,请使用以下格式:
第一行应包含一个整数 $$$t$$$ — 测试用例的数量 ($$$1 \leq t \leq 10^3$$$)。
每个测试用例的第一行应包含一个整数 $$$n$$$ ($$$2 \leq n \leq 10^5$$$)。
每个测试用例的第二行应包含 $$$n$$$ 整数 $$$a_1,a_2,\ldots,a_n$$$ ($$$1 \leq a_1 \lt a_2 \lt \ldots \lt a_n \leq 4n$$$) – 指示每条蛇的位置。
每个测试用例的第三行应包含 $$$n$$$ 整数 $$$s_1,s_2,\ldots,s_n$$$ ($$$0 \leq s_i \leq 2$$$) – 表示每条蛇的速度。
所有测试用例的 $$$n$$$ 总和不应超过 $$$10^5$$$。
$$$^{\text{*}}$$$要刷新,请使用:
- fflush(标准输出) or cout.flush() 在 C++ 中;
- sys.stdout.flush() 在 Python 中;
- 请参阅其他语言的文档。
示例
输入复制
7 2 1 2 1 1 2 1 6 2 1 4 3 2 3 4 2 2 4 3 2 3 4 3 5 6 7 5 1 3 8 14 15 5 1 2 3 4 5 4 5 6 7 8
输出复制
? L ! 0 1 ? LRLL ! 0 1 ? RRR ! -1 ? RRR ! 1 1 1 ! 2 1 0 0 1 ! 0 2 2 2 0 ! 0 1 2 0
注意
在第一个测试用例中,蛇的速度为 $$$0$$$ 和 $$$1$$$。程序首先给出指令 L。右侧的蛇从 $$$2$$$ 移动到 $$$1$$$,而左侧的蛇则不动。然而,由于现在两条蛇都占据了位置 $$$1$$$,因此速度较高的蛇(右侧蛇)将被移除。因此,只剩下一条蛇,它位于位置$$$1$$$。此时,程序决定将蛇的速度猜测为 $$$0$$$ 和 $$$1$$$,这是正确的,因此该测试用例通过。请注意,虽然速度 $$$[0,2]$$$ 也会导致在位置 $$$1$$$ 处出现 $$$1$$$ 蛇,但我们不能报告 $$$-1$$$,因为我们可以显示有一系列指令可以区分 $$$[0,2]$$$ 和 $$$[0,1]$$$。
在第三个测试用例中,我们得出结论,第一条蛇和第三条蛇的速度都是$$$0$$$,并且我们可以证明没有办法区分$$$1$$$和$$$2$$$之间中间一条蛇的速度。因此,报告 -1 在这种情况下是正确的。