CF2183G.Snake Instructions

This is an interactive problem.

There are $n$ snakes on the number line. The $i$-th snake is located at the position $a_i$ and has a speed $s_i$. You know the position of each snake, and that the speed of each snake is an integer from $0$ to $2$ inclusive, but you do not know the exact speed of each snake. It is guaranteed that no two snakes are at the same position.

To figure out the snakes' speed, you may give up to $3$ instructions. Each instruction should be given in the form of a binary string of length $m$ containing letters L and R ($1 \leq m \leq 4n$). After receiving this instruction, the snakes will move for $m$ seconds. On the $i$-th second, if $s_i=$L, then all snakes move left for that second. Otherwise, all snakes move right for that second. If two snakes are at the same location at any given point (including if the time is not an integer number of seconds), the faster snake is removed from the board. After all $m$ seconds have passed, you are given the number of remaining snakes, as well as the location of all remaining snakes. Note that each instruction is independent of each other – that means that all snakes are revived and moved to their original positions.

Your task is to find the speed of all snakes. However, it may be the case that it is impossible to find the speed of at least one snake. If this is the case, you must report -1 instead. You should only output -1 if it is impossible to figure out the speed of at least one snake, no matter which instructions are given. If you report -1 when there are a series of at most $3$ instructions that will uniquely determine the speed of each snake, you will get the Wrong Answer verdict. Similarly, you will receive the Wrong Answer verdict if you did not report -1 when the configuration is impossible to determine, even if you correctly guessed the speeds.

这是一个交互式问题。

数轴上有 $n$ 条蛇。第 $i$ 条蛇位于位置 $a_i$，其速度为 $s_i$。你已知每条蛇的位置，且每条蛇的速度是 $0$ 到 $2$（含）之间的整数，但你并不知道每条蛇的确切速度。保证任意两条蛇初始位置互不相同。

为了确定各条蛇的速度，你最多可以发出 $3$ 条指令。每条指令应是一个长度为 $m$ 的二进制字符串（$1 \leq m \leq 4n$），仅由字母 L 和 R 组成。收到该指令后，所有蛇将移动 $m$ 秒：在第 $i$ 秒，若指令中第 $i$ 个字符为 L，则所有蛇向左移动；否则（即为 R），所有蛇向右移动。若在任意时刻（包括非整数秒的时刻）有两条蛇位于同一位置，则速度较快者将被从数轴上移除。当全部 $m$ 秒结束后，你会获知剩余蛇的数量，以及所有剩余蛇的位置。注意：每次指令彼此独立——这意味着每次指令开始前，所有蛇都会复活并回到其原始初始位置。

你的任务是确定每条蛇的速度。然而，有可能至少有一条蛇的速度无法被唯一确定。若出现这种情况，你必须输出 -1。仅当无论采用何种指令序列，都必然无法确定至少一条蛇的速度时，才应输出 -1。如果你在实际上存在一组不超过 $3$ 条指令、足以唯一确定所有蛇速度的情况下错误地输出了 -1，则判为“答案错误”（Wrong Answer）。类似地，若该蛇的配置本质上无法被完全确定（即无论如何都无法唯一确定所有蛇的速度），而你未输出 -1（哪怕你恰好猜对了所有速度），同样判为“答案错误”。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^3$). The description of the test cases follows.

The first line of each test case contains an integer $n$ – the number of snakes ($2 \leq n \leq 10^5$).

The second line contains $n$ integers $a_1,a_2,\ldots,a_n$ ($1 \leq a_1 \lt a_2 \lt \ldots \lt a_n \leq 4n$) – the initial position of all snakes.

It is guaranteed that the sum of $n$ across all test cases does not exceed $10^5$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $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$。

In the first test case, the speed of the snakes is $0$ and $1$. The program begins by giving the instruction L. The right snake moves from $2$ to $1$ while the left snake does not move. However, since now both snakes occupy the position $1$, the one with the higher speed (the right snake) is removed. Therefore, there is only one snake remaining, and it is at position $1$. At this point, the program decides to guess the speed of snakes as $0$ and $1$, which is correct, so this test case is passed. Note that although the speeds $[0,2]$ would also result in there being $1$ snake at position $1$ at the end, we cannot report $-1$, as we can show there is a series of instructions that will differentiate $[0,2]$ and $[0,1]$.

In the third test case, we conclude that the speed of both the first snake and the third snake is $0$, and we can show there is no way to differentiate the speed of the middle snake between $1$ and $2$. Therefore, reporting -1 is correct in this case.

在第一个测试用例中，蛇的速度分别为 $0$ 和 $1$。程序首先发出指令 L。右侧的蛇从位置 $2$ 移动到 $1$，而左侧的蛇保持不动。此时，两条蛇均位于位置 $1$，因此速度较高者（即右侧的蛇）被移除。最终仅剩一条蛇，位于位置 $1$。此时，程序判断蛇的速度为 $0$ 和 $1$，该判断正确，因此该测试用例通过。注意：虽然速度组合 $[0,2]$ 同样会导致最终仅剩一条蛇且位于位置 $1$，但我们不能输出 $-1$，因为我们能够构造出一组指令，将 $[0,2]$ 与 $[0,1]$ 区分开来。

在第三个测试用例中，我们推断出第一条蛇和第三条蛇的速度均为 $0$，并且可以证明：无法区分中间那条蛇的速度究竟是 $1$ 还是 $2$。因此，本例中输出 $-1$ 是正确的。