P16192 [COI 2018] Zagonetka 谜题

3s，1024MB。

Mislav 和 Marin 在组合数学课上学到了排列的知识，他们发明了一个有趣的游戏：玩家需要猜出满足特定条件的排列。一个阶数为 $n$ 的 *排列*，是一个数组 $p = (p_1, p_2, \ldots , p_n)$，其中数字 $1$ 到 $n$ 各出现一次且仅出现一次。一个 *条件* 是一对不同的数字 $(a, b)$，两者都在 $1$ 到 $n$ 之间。排列 $p$ 满足条件 $(a, b)$ 当且仅当 $p_a < p_b$。 游戏玩法如下：Marin 先选定零个或多个条件，以及一个满足所有条件的排列 $p$。游戏开始时，Marin 只告诉 Mislav 这个排列 $p$（条件保密）。Mislav 的目标是找出所有满足条件的排列中字典序最小和字典序最大的两个排列。在每一步，Mislav 选择一个排列 $q$ 并发送给 Marin，Marin 会告诉他这个排列 $q$ 是否满足所有秘密条件。 这是一个交互式任务。请编写程序代替 Mislav 玩这个游戏。给定一个满足秘密条件的排列 $p$（长度最多为 $100$），你的程序最多可进行 $5000$ 次查询，找出满足所有条件的字典序最小和字典序最大的排列。

### 交互说明 交互开始时，你的程序需要从标准输入读取以下内容：第一行是整数 $n$——游戏中所有排列的阶。接下来一行包含 $n$ 个不同的整数 $p_1, p_2, \ldots , p_n\ (1 \le p_j \le n)$，表示排列 $p$。你可以假设 $p$ 满足 Marin 设定的所有条件。 之后，你的程序可以向 Marin 发送查询，每个查询输出一行，格式为 “`query` $q_1\ q_2\ ...\ q_n$”，其中 $q_1, q_2,\ldots, q_n$ 是 $1$ 到 $n$ 的不同整数。每次查询后，必须 *刷新* 输出缓冲区，然后从标准输入读取 Marin 的回复：如果排列 $q$ 满足所有条件，返回 $1$，否则返回 $0$。 当你的程序找到答案时，输出一行 `end`，接着输出一行包含字典序最小的排列 $a_1\ a_2 \ \ldots\ a_n$，再输出一行包含字典序最大的排列 $b_1\ b_2 \ldots \ b_n$。最后刷新输出并结束程序。 注意：评测系统提供了示例代码，演示了如何正确进行交互并刷新输出。

无

### 示例 下面的交互示例中，左栏是你的程序输出到标准输出的内容，右栏是从标准输入读取的内容。经过三次查询后，程序找到了正确答案。 |输出 |输入 |说明 | |:--------:|:-------:|:--------:| | |`4` |秘密条件是 $(2, 1)$ 和 $(3, 4)$| | |`3 2 1 4`| | |`query 2 3 1 4`|`0` |条件 $(2, 1)$ 不满足| |`query 3 2 4 1`|`0` |条件 $(3, 4)$ 不满足| |`query 4 1 2 3`|`1` |两个条件都满足 | |`end` | | | |`2 1 3 4` | | | |`4 3 1 2` | | | ### 子任务 ::cute-table{three} |编号 |分值 |约束条件 | |:-:|:--:|:--------:| |$1$|$9$ |$2 \le n \le 6$| |$2$|$18$|$30 \le n \le 70$，Marin 只选了 $1$ 个条件| |$3$|$22$|$10 \le n < 30$| |$4$|$51$|$70 < n \le 100$| 翻译来源：GPT 4.1 mini。