시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 256 MB | 39 | 9 | 6 | 18.750% |
This is an interactive problem.
There is a secret permutation $p$ of integers from $0$ to $n - 1$. The permutation is indexed starting from $0$. You have to guess it by asking questions of the form "? $a_i$ $b_i$ $c_i$" ($a_i$, $b_i$ and $c_i$ are integers from $0$ to $n - 1$). For each such question, you will get one number in response which equals $p^{-1} (p (a_i) \cdot p (b_i) + p (c_i))$ (all operations are performed modulo $n$, and $p^{-1} (x)$ is such $y$ that $p (y) = x$). In the end, you have to print the guessed permutation in the form "! $p (0)$ $p (1)$ $\ldots$ $p (n - 1)$".
The only line of the input contains an integer $n$ ($1 \leq n \leq 5 \cdot 10^3$).
In each test, the permutation is fixed in before the contest and does not change during the guessing process.
For each test, the length $n$ was picked by the jury, but the permutation was then generated using a pseudorandom number generator. However, the problem has a deterministic solution which works for every possible permutation.
You can ask zero or more questions and make exactly one guess in the end. Print each query on a separate line and do not forget to flush the output buffer. The maximum allowed number of queries, including the final guess, is $12\,512$.
4 3 2 1
? 1 2 3 ? 0 3 3 ? 0 0 1 ! 2 0 3 1
Camp > Petrozavodsk Programming Camp > Summer 2017 > Day 3: Ural Contest F번
Contest > Open Cup > 2017/2018 Season > Stage 2: Grand Prix of Ural F번