P9470 [EGOI 2023] Guessing Game / Guessing Game (interactive problem cannot be judged)

Day 2 Problem D. Translated from [EGOI2023 guessinggame](https://egoi23.se/assets/tasks/day2/guessinggame.pdf)。 [](https://creativecommons.org/licenses/by-sa/3.0/)

**This is an interactive problem.** In the old town of Lund, there is a street with $N$ houses in a row, numbered from $0$ to $N-1$. Emma lives in one of the houses, and her friends Anna and Bertil want to find out which one it is. Emma decides to play a game with them instead of telling them directly where she lives. Before the game starts, Anna and Bertil only know the number of houses on the street. At this point, Anna and Bertil may choose a positive integer $K$ and fix a strategy. After that, any communication is forbidden. The game itself has two phases. In the first phase, Emma chooses an order in which to visit the houses, such that her own house is visited last. Then, she leads Anna to visit the houses one by one in this order, without telling Anna the order in advance. For each house that is not Emma’s house, Anna is allowed to write an integer from $1$ to $K$ on the front door using chalk. For the last house they visit, which is Emma’s house, Emma herself writes an integer from $1$ to $K$ on the door. In the second phase, Bertil walks along the street, visiting the houses in order from $0$ to $N-1$, and reads the numbers written by Anna and Emma on the doors. He then wants to guess Emma’s house. He has two chances to guess. If he guesses correctly, he and Anna win the game. Otherwise, Emma wins. Can you give a strategy so that Anna and Bertil are guaranteed to win? Your strategy will be scored based on the value of $K$ (smaller is better).

N/A

This is an interactive problem, meaning your program will be run multiple times. The first run executes Anna’s strategy. Afterwards, it executes Bertil’s strategy. The first line of input contains two integers $P$ and $N$, where $P$ is $1$ or $2$ (first phase or second phase), and $N$ is the number of houses. **Except for the sample input (which is not used for scoring), $N$ is always $10^5$.** The rest of the input depends on the phase: **First phase** Your program should first output an integer $K$ followed by a newline ($1\le K\le 10^6$). Then, repeat $N-1$ times: read one integer $i$ ($0\le i < N$) from one line, and output one integer $A_i$ ($1\le A_i\le K$) on one line, where $A_i$ is the number Anna writes on the door of house $i$. Each integer $i$ (except Emma’s house) will appear exactly once, in an order decided by the interactive library. **Second phase** Your program should read one line containing $N$ integers $A_0,A_1,\cdots,A_{N-1}$, where $A_i$ is the number written on the door of house $i$. Then output one line with two integers $s_1$ and $s_2$ ($0\le s_i < N$), representing the two guessed house indices. $s_1$ and $s_2$ are allowed to be equal. **Implementation details** Note that when your program runs in the second phase, it is restarted. This means you cannot store information between the two phases in variables. Make sure to flush the output stream after each line, otherwise your program may be judged as TLE. In Python, `print()` flushes automatically. In C++, `cout

**Sample explanation** Sample testcases are not included in the total score, and your program does not need to support the sample testcases. Suppose we have $N=4$ and Emma lives in house $1$. Let $A$ be the list of numbers written on each house. Initially, $A=[0,0,0,0]$, where $0$ means that the corresponding house has not been written on yet. In the first run: Given $N=4$. Your program answers $K=3$. $A_2$ is requested. Your program answers $3$. $A$ is now $[0,0,3,0]$. $A_0$ is requested. Your program answers $1$. $A$ is now $[1,0,3,0]$. $A_3$ is requested. Your program answers $2$. $A$ is now $[1,0,3,2]$. Finally, the interactive library sets $A_1=2$, so $A=[1,2,3,2]$. This marks the end of the first phase. In the second phase, your program is given the list `1 2 3 2`. Your program answers `1 3`. Since one of the guesses is correct ($1$), Anna and Bertil win the game. --- **Scoring** Your program will be tested on a number of testcases. If your program fails on *any* testcase (for example: gives a wrong answer (WA), crashes (RE), exceeds the time limit (TLE), etc.), you will receive $0$ points and the corresponding verdict. If your program successfully finds Emma’s house on *all* testcases, you will get AC (**translator’s note: on Luogu, anything that is not full score is considered WA**), and the score is computed as follows. Let $K_{\max}$ be the maximum value of $K$ over all testcases. Based on $K_{\max}$: ||Score| |:-|:-| |$K_{\max} > 99998$|$10$| |$10000 < K_{\max}\le 99998$|$10+\lfloor40(1-\frac{K_{\max}}{10^5})\rfloor$| |$30 < K_{\max}\le 10000$|$46+\lfloor\frac{31(4-\lg K_{\max})}{4-\lg 30}\rfloor$| |$7 < K_{\max}\le 30$|$107-K_{\max}$| |$K_{\max}\le 7$|$100$| The graph of the scoring function is as follows:  Sample testcases are not included in the total score, and your program does not need to support the sample testcases. Translated by ChatGPT 5