CF2183G Snake Instructions

这是一个交互题。 数轴上有 $n$ 条蛇。第 $i$ 条蛇在位置 $a_i$，速度为 $s_i$。你已知每条蛇的位置，并且每条蛇的速度是 $0$ 到 $2$ 的整数，但你不知道具体每条蛇的速度。保证没有两条蛇处于相同的位置。 为了确定所有蛇的速度，你最多可以进行 $3$ 次指令。每条指令应以长度为 $m$ 的二进制字符串给出，字符串只包含 L 和 R （$1 \leq m \leq 4n$）。收到这条指令后，所有蛇会运动 $m$ 秒。在第 $i$ 秒，如果 $s_i=$ L，则所有蛇向左运动一秒，否则全部蛇向右运动一秒。如果在某一时刻（包括非整数秒时），有两条蛇处于相同的位置，则速度快的那条蛇被移除。$m$ 秒后，你会获得剩下的蛇的数量 $k$，以及所有剩余蛇的位置。注意，每次指令都是独立的——也就是说，所有蛇都会复活回到起始位置再开始新的操作。 你的任务是确定所有蛇的速度。然而，可能存在无法确定某一条蛇的速度的情况，如果碰到这种情况，你需要输出 $-1$。只有当无论给出哪一组最多 $3$ 条指令都无法确定某条蛇的速度时，才能输出 $-1$。如果存在至多 $3$ 条指令能唯一确定所有蛇的速度而你输出了 $-1$，你会得到 Wrong Answer 判决。同理，如果本应该输出 $-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

**交互说明** 读入所有蛇的位置后，开始交互。每次发出指令需按以下格式输出一行： - `? s` 你需保证 $s$ 只由字母 `L` 和 `R` 组成，且长度在 $1$ 到 $4n$ 之间。 评测器会返回如下格式的一行： - $k\ b_1\ b_2\ \ldots\ b_k$（$1 \leq k \leq n, -10^9 \leq b_1

在第一个用例中，两条蛇速度分别为 $0$ 和 $1$。程序首先给出指令 L。右边那条蛇从 $2$ 移动到 $1$，而左边的蛇不动。此时两条蛇都在 $1$，速度较大的蛇（右边那只）被移除。因此只剩下一条蛇在位置 $1$。此时程序猜测两条蛇的速度分别为 $0$ 和 $1$，这是正确的。注意，尽管速度 $[0,2]$ 也会导致最后只剩一只蛇在 $1$，但不能直接输出 $-1$，因为还可以通过另一组指令区分 $[0,2]$ 和 $[0,1]$。 在第三个用例中，可以确定第一条蛇和第三条蛇的速度均为 $0$，且可以证明无论如何无法区分中间那条蛇的速度是 $1$ 还是 $2$，因此输出 $-1$ 是正确的。 由 ChatGPT 5 翻译