시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 (추가 시간 없음) | 512 MB | 18 | 7 | 7 | 46.667% |
This is an interactive problem.
Jury has chosen a secret odd number $x$ between $1$ and $2^{31}-1$ inclusive. Your task is to guess it. In order to do that, jury gives you an even number $n$. Then you should output exactly $n$ distinct integers between $0$ and $2^{31}-1$ inclusive. After that, jury will multiply each of these numbers by $x$ and take the results modulo $2^{31}$. Then jury will equiprobably choose some random subset of these new numbers of size $n/2$ and give this subset back to you in random order. After that, you should output the correct value of $x$.
In each test, $x$ is chosen in advance and does not change.
Initially, you are given one even integer $n$ ($4 \leq n \leq 10^5$). After that, you should output $n$ distinct integers $a_1, a_2, \ldots, a_n$ ($0 \leq a_i \leq 2^{31}-1$) on a single line, separated by spaces. Next, you are given $n/2$ integers $b_1, b_2, \ldots, b_{n/2}$ ($0 \leq b_i \leq 2^{31}-1$) created by the process described above, on a single line, separated by spaces. Finally, you should output a single odd integer $x$: the secret number chosen by the jury ($1 \leq x \leq 2^{31}-1$).
To prevent output buffering, flush the output buffer after each printed line: this can be done by using, for example, fflush (stdout)
in C or C++, System.out.flush ()
in Java, flush (output)
in Pascal, or sys.stdout.flush ()
in Python. Also, do not forget to terminate each line of output with a newline character.
4 9 6
1 2 3 4 3