P16192 [COI 2018] Zagonetka Puzzle

3 s, 1024 MB.

Mislav and Marin learned about permutations in a combinatorics class, and they invented an interesting game: the player needs to guess permutations that satisfy certain conditions. A *permutation* of order $n$ is an array $p = (p_1, p_2, \ldots, p_n)$ in which each number from $1$ to $n$ appears exactly once. A *condition* is a pair of distinct numbers $(a, b)$, both between $1$ and $n$. A permutation $p$ satisfies the condition $(a, b)$ if and only if $p_a < p_b$. The game works as follows: Marin first chooses zero or more conditions, and a permutation $p$ that satisfies all of them. When the game starts, Marin tells Mislav only this permutation $p$ (the conditions are kept secret). Mislav’s goal is to find the lexicographically smallest and the lexicographically largest permutations among all permutations that satisfy the conditions. In each step, Mislav chooses a permutation $q$ and sends it to Marin, and Marin tells him whether $q$ satisfies all the secret conditions. This is an interactive task. Write a program to play this game on behalf of Mislav. Given a permutation $p$ (of length at most $100$) that satisfies the secret conditions, your program may make at most $5000$ queries to find the lexicographically smallest and the lexicographically largest permutations that satisfy all conditions.

### Interaction At the beginning of the interaction, your program must read the following from standard input: the first line contains an integer $n$, the order of all permutations in the game. The next line contains $n$ distinct integers $p_1, p_2, \ldots, p_n\ (1 \le p_j \le n)$, representing the permutation $p$. You may assume that $p$ satisfies all conditions chosen by Marin. After that, your program can send queries to Marin. For each query, output one line in the format `query` $q_1\ q_2\ ...\ q_n$, where $q_1, q_2, \ldots, q_n$ are distinct integers from $1$ to $n$. After each query, you must *flush* the output buffer, and then read Marin’s reply from standard input: if the permutation $q$ satisfies all conditions, the reply is $1$, otherwise it is $0$. When your program has found the answer, output one line `end`, then output one line containing the lexicographically smallest permutation $a_1\ a_2 \ \ldots\ a_n$, and then output one line containing the lexicographically largest permutation $b_1\ b_2 \ldots \ b_n$. Finally, flush the output and terminate. Note: the judging system provides sample code that demonstrates how to interact correctly and flush the output.

N/A

### Example In the following interaction example, the left column is what your program outputs to standard output, and the right column is what it reads from standard input. After three queries, the program found the correct answer. |Output |Input |Explanation | |:--------:|:-------:|:--------:| | |`4` |The secret conditions are $(2, 1)$ and $(3, 4)$| | |`3 2 1 4`| | |`query 2 3 1 4`|`0` |Condition $(2, 1)$ is not satisfied| |`query 3 2 4 1`|`0` |Condition $(3, 4)$ is not satisfied| |`query 4 1 2 3`|`1` |Both conditions are satisfied| |`end` | | | |`2 1 3 4` | | | |`4 3 1 2` | | | ### Subtasks ::cute-table{three} |ID |Score |Constraints | |:-:|:--:|:--------:| |$1$|$9$ |$2 \le n \le 6$| |$2$|$18$|$30 \le n \le 70$, Marin chose only $1$ condition| |$3$|$22$|$10 \le n < 30$| |$4$|$51$|$70 < n \le 100$| Translation source: GPT 4.1 mini. Translated by ChatGPT 5