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.

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

**Interaction** After reading in the position of all snakes, interaction begins. To give an instruction, output a line in the following format: - `? s` You should guarantee that $s$ contains only letters `L` and `R`, and has length between $1$ and $4n$ inclusive. The jury will return a line in the following format: - $k\ b_1\ b_2\ \ldots\ b_k$ ($1 \leq k \leq n, -10^9 \leq b_1

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.