1867C.md (3830B)
1 Source: https://codeforces.com/problemset/problem/1867/C 2 3 C. Salyg1n and the MEX Game 4 5 time limit per test 6 7 3 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 This is an interactive problem! 22 23 salyg1n gave Alice a set $S$ of $n$ distinct integers $s_1, s_2, \ldots, s_n$ ($0 \leq s_i \leq 10^9$). Alice decided to play a game with this set against Bob. The rules of the game are as follows: 24 25 * Players take turns, with Alice going first. 26 * In one move, Alice adds one number $x$ ($0 \leq x \leq 10^9$) to the set $S$. The set $S$ must not contain the number $x$ at the time of the move. 27 * In one move, Bob removes one number $y$ from the set $S$. The set $S$ must contain the number $y$ at the time of the move. Additionally, the number $y$ must be strictly smaller than the last number added by Alice. 28 * The game ends when Bob cannot make a move or after $2 \cdot n + 1$ moves (in which case Alice's move will be the last one). 29 * The result of the game is $\operatorname{MEX}\dagger(S)$ ($S$ at the end of the game). 30 * Alice aims to maximize the result, while Bob aims to minimize it. 31 32 Let $R$ be the result when both players play optimally. In this problem, you play as Alice against the jury program playing as Bob. Your task is to implement a strategy for Alice such that the result of the game is always at least $R$. 33 34 $\dagger$ $\operatorname{MEX}$ of a set of integers $c_1, c_2, \ldots, c_k$ is defined as the smallest non-negative integer $x$ which does not occur in the set $c$. For example, $\operatorname{MEX}(\{0, 1, 2, 4\})$ $=$ $3$. 35 36 Input 37 38 The first line contains an integer $t$ ($1 \leq t \leq 10^5$) - the number of test cases. 39 40 Interaction 41 42 The interaction between your program and the jury program begins with reading an integer $n$ ($1 \leq n \leq 10^5$) - the size of the set $S$ before the start of the game. 43 44 Then, read one line - $n$ distinct integers $s_i$ $(0 \leq s_1 \lt s_2 \lt \ldots \lt s_n \leq 10^9)$ - the set $S$ given to Alice. 45 46 To make a move, output an integer $x$ ($0 \leq x \leq 10^9$) - the number you want to add to the set $S$. $S$ must not contain $x$ at the time of the move. Then, read one integer $y$ $(-2 \leq y \leq 10^9)$. 47 48 * If $0 \leq y \leq 10^9$ - Bob removes the number $y$ from the set $S$. It's your turn! 49 * If $y$ $=$ $-1$ - the game is over. After this, proceed to handle the next test case or terminate the program if it was the last test case. 50 * Otherwise, $y$ $=$ $-2$. This means that you made an invalid query. Your program should immediately terminate to receive the verdict Wrong Answer. Otherwise, it may receive any other verdict. 51 52 After printing a query do not forget to output the end of line and flush the output. Otherwise, you will get Idleness limit exceeded. To do this, use: 53 54 * fflush(stdout) or cout.flush() in C++; 55 * System.out.flush() in Java; 56 * flush(output) in Pascal; 57 * stdout.flush() in Python; 58 * see the documentation for other languages. 59 60 It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$. 61 62 Do not attempt to hack this problem. 63 64 Example 65 66 Input 67 68 ``` 69 3 70 5 71 1 2 3 5 7 72 73 7 74 75 5 76 77 -1 78 79 3 80 0 1 2 81 82 0 83 84 -1 85 86 3 87 5 7 57 88 89 -1 90 ``` 91 92 Output 93 94 ``` 95 8 96 97 57 98 99 0 100 101 3 102 103 0 104 105 0 106 ``` 107 108 Note 109 110 In the first test case, the set $S$ changed as follows: 111 112 {$1, 2, 3, 5, 7$} $\to$ {$1, 2, 3, 5, 7, 8$} $\to$ {$1, 2, 3, 5, 8$} $\to$ {$1, 2, 3, 5, 8, 57$} $\to$ {$1, 2, 3, 8, 57$} $\to$ {$0, 1, 2, 3, 8, 57$}. In the end of the game, $\operatorname{MEX}(S) = 4$, $R = 4$. 113 114 In the second test case, the set $S$ changed as follows: 115 116 {$0, 1, 2$} $\to$ {$0, 1, 2, 3$} $\to$ {$1, 2, 3$} $\to$ {$0, 1, 2, 3$}. In the end of the game, $\operatorname{MEX}(S) = 4$, $R = 4$. 117 118 In the third test case, the set $S$ changed as follows: 119 120 {$5, 7, 57$} $\to$ {$0, 5, 7, 57$}. In the end of the game, $\operatorname{MEX}(S) = 1$, $R = 1$.