E. Experiment! AMOGUS Edition
time limit per test
5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
This is an interactive problem.

It is the end of the year 2023. Alice still shouts AMOGUS at the top of her lungs. She believes it to be the funniest joke ever created in all of human history. She has even purchased an inflatable Amogus costume, which she will treasure for years to come. Truly, Amogus is eternal.

The Earth's greatest scientists have designed a new mod of the game, which introduces an interesting twist to the mechanics. Alice has been hired as one of their playtesters, and her job is to determine whether or not this mod is actually fun.

  • A lobby can contain an arbitrary number of players—let's call this number $$$n$$$.
  • Exactly one player is (secretly) chosen to be the imposter.
  • Another different player is (secretly) chosen to be the witness—the witness knows who the imposter is at the start of the game.
  • Alice always chooses a special role called the detective; the detective is not a player.
Up to $$$k$$$ times, the detective may call an emergency meeting, where they choose a subset of the players and interrogate them. This is the chance for the witness to tell the detective who the imposter is, but there is a twist—if the imposter is also in that same emergency meeting, then the witness is frightened into silence and cannot speak. Formally:
  • If the witness is present and the imposter is not, then the detective learns the identity of the imposter.
  • If both the witness and the imposter are present, then nothing happens.
  • In all other cases, nothing happens as well.
Alice wants to know how big of a lobby is possible (i.e. the maximum value of $$$n$$$) such that it is always possible to determine the identity of the imposter using only the $$$k$$$ meetings. She has a solution already (she has an IQ of $$$10^{100}$$$ after all) but wants you to independently solve this problem as well, to verify her approach.
Interaction

The judge first outputs a single integer $$$k$$$, the number of emergency meetings. For this problem, $$$k=18$$$ always.

Next, you should output a single integer $$$n$$$, the number of players you wish to invite to your lobby; this $$$n$$$ should be at least $$$2$$$ and at most $$$5 \times 10^4$$$. In general, the higher this $$$n$$$, the better your score will be. The players are indexed from $$$1$$$ to $$$n$$$.

The following interaction then plays out up to $$$k$$$ times:

  • The detective calls an emergency meeting; you should tell the judge whom you want to invite to this meeting.
    • First, output a single positive integer $$$t$$$, the number of players called to the meeting.
    • Then, output $$$t$$$ distinct space-separated integers (each from $$$1$$$ to $$$n$$$), the indices of the players invited to the meeting.
  • Then, the judge responds with the outcome of the meeting.
    • If the witness was invited to the meeting and the imposter was not, the judge responds with <W> REPORTS <I>, where <W> is the index of the witness, and <I> is the index of the killer. If this happens, your program was succesful, and then no further messages will be sent from the judge, so you should exit immediately.
    • In any other case, the judge responds with a line containing SILENCE... and you should proceed with the next emergency meeting.
If $$$k$$$ rounds pass with a SILENCE... verdict in all interactions, then the judge sends the message DEFEAT in its own line, and then then message <W> WAS WITNESS, <I> WAS IMPOSTER (to prove that there was a solution).

In this problem, the judge is adaptive! Basically, the judge is designed so that it is impossible for your program to "get lucky" and succeed by sheer coincidence. The judge will always trigger the "unluckiest" worst case scenario for your algorithm, and will only Accept your solution if your algorithm works 100% of the time, no matter what. You may refer to the Notes section for a bit more detail.

Scoring

If your solution is incorrect, you get $$$0$$$ points. If correct, you are awarded points based on the size of $$$n$$$ outputted in the successful attempt. $$$$$$\begin{align*}

&\begin{array}{|c|c|l|} \hline \text{Subtask} & \text{Points} & \text{Constraints} \\ \hline 1 & \mathbf{35} & n \geq 18 \\ \hline 2 & \mathbf{15} & n \geq 30 \\ \hline 3 & \mathbf{10} & n \geq 80 \\ \hline 4 & \mathbf{26} & n \geq 500 \\ \hline 5 & \mathbf{6} & n \geq 700 \\ \hline 6 & \mathbf{8} & n \geq 48000 \\ \hline \end{array}\\

\end{align*}$$$$$$

Note

Here is how the adaptive judge decides on how to act. Basically, the judge does not actually select the witness and imposter in advance. The adaptive judge will try to respond with SILENCE... whenever possible, so long as it "maintains plausible deniability", i.e. so long as there still exists any selection of witness and imposter that is consistent with all its responses so far. Informally, the judge is a cheater, but will never let itself get caught (and will give you the win if you manage to checkmate it).

Here is a sample interaction: 


Judge           Contestant
18
                4
                2
                1 2
SILENCE...
                3
                1 3 4
SILENCE...
                2
                2 3
SILENCE...
                1
                4
4 REPORTS 1
Here, the solution claims to be able to find the witness and imposter among a lobby with $$$4$$$ players. Note that once the game has been won, the rest of the rounds don't play out any more.