Background

Day 2 Problem D.

Translated from EGOI2023 guessinggame。

Problem Description

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).

Output Format

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 << endl; flushes after printing the newline; if you use printf, use fflush(stdout).

The interactive library may be adaptive, meaning it may change its behavior based on your program’s output, to prevent heuristic solutions from passing. It may run the first phase once, observe your output, then run the first phase again based on what it was able to extract from your output.

Your program must be deterministic, meaning that running it twice on the same input must produce the same output. If you want to use randomness, make sure to use a fixed random seed. You can do this by passing a hard-coded constant to srand (in C++) or random.seed (in Python), or, if you use a C++11 random generator, by fixing the seed when constructing it. In particular, you cannot use srand(time(NULL)) in C++. If the interactive library detects that your program is not deterministic, it may be judged as WA.

If the sum of running times of each independent run (up to $3$ runs in total) exceeds the time limit, it will be judged as TLE.

1 4

2

0

3

3

3

1

2

2 4
1 2 3 2

1 3

Hint

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}$:

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