自行车比赛 - 题目

有 $N$ 名自行车手，编号为 $1, \dots, N$。每名车手都有一个 $1$ 到 $N$ 之间互不相同的技能值，当两名车手对决时，技能值较高的车手总是获胜。

车手们喜欢参加比赛。在比赛中，车手们按环形列表排列。比赛分轮进行。在每一轮中，每名车手都会与他们的邻居进行比赛。如果一名车手输给了两名邻居，他就会被淘汰。

你不知道车手们的技能值，但想要找出它们。你可以组织多场比赛，每次选择车手在环形列表中的排列方式，并会获知每名车手是在哪一轮被淘汰的。

请使用最少次数的比赛来找出所有车手的技能值，或者使用 $N$ 次比赛以获得部分分数。

每个测试点包含多个测试用例。交互开始时，输入包含一个整数 $T$ ($1 \le T \le 10^4$)，表示测试用例的数量。

每个测试用例开始时，输入包含一个整数 $N$ ($3 \le N \le 300$)，表示车手的数量。

之后你可以进行比赛。要进行一场比赛，请输出一行 “? $a_1$ $a_2$ $\dots$ $a_n$” —— $a_k$ 表示车手 $a_k$ 位于车手列表的第 $k$ 个位置。列表 $a_1, \dots, a_n$ 必须是 $1, \dots, n$ 的一个排列。

查询的回答将是一行 “$r_1$ $r_2$ $\dots$ $r_n$” —— $r_k$ 满足 $0 \le r_k < n$。当 $r_k > 0$ 时，表示位于第 $k$ 个位置的车手在比赛的第 $r_k$ 轮被淘汰。如果 $r_k = 0$，则表示该车手赢得了比赛。

当你确定了所有车手的技能值后，请输出一行 “! $s_1$ $s_2$ $\dots$ $s_n$” —— $s_k$ 应等于车手 $k$ 的技能值。

如果你进行了无效的查询或尝试进行超过 $N$ 次比赛，你的程序将收到 Wrong Answer 判决。此外，如果你输出的技能集合与交互器预设的技能集合不同，你的程序也将收到 Wrong Answer 判决。在这两种情况下，交互都会立即终止。否则，你将根据评分部分获得分数。

注意，交互器可能是自适应的：车手们的真实技能值可能会在交互过程中发生变化，但当前的技能集合始终与之前所有的比赛结果保持一致。

对于每个测试用例，设 $q$ 为你的程序进行的比赛次数。此外，对于每个 $N$，设 $c_N$ 为保证能够确定技能值所需的最少比赛次数。

如果对于所有测试用例都有 $q \le c_N$，你将获得 100 分。否则，你将获得 10 分。注意，根据题目限制，获得 10 分要求对于所有测试用例满足 $q \le N$。

1
5 Fixed
4 2 1 5 3
? 1 2 3 4 5
3 2 1 0 1
? 1 3 5 2 4
3 1 2 1 0
? 1 4 2 5 3
3 0 1 2 1
? 1 5 4 3 2
3 1 0 1 2
! 4 2 1 5 3

>>> 1
>>> 5

在样例中，车手的技能值分别为 $4, 2, 1, 5, 3$。

在第一场比赛中，车手按列表 $[1, 2, 3, 4, 5]$ 排列。比赛过程如下；每一轮中，车手列表显示如下，被淘汰的车手用 $X$ 代替。

第 1 轮：
- 第 3 个位置的车手（技能为 1 的车手 3）输给了第 2 和第 4 个位置的车手（技能分别为 2, 5 的车手 2, 4），被淘汰。
- 第 5 个位置的车手（技能为 3 的车手 5）输给了第 4 和第 1 个位置的车手（技能分别为 5, 4 的车手 4, 1），被淘汰。
- 第 1 个位置的车手（技能为 4 的车手 1）击败了第 5 和第 2 个位置的车手（技能分别为 3, 2 的车手 5, 2），未被淘汰。
- 第 2 个位置的车手（技能为 2 的车手 2）击败了第 3 个位置的车手（技能为 1 的车手 3），未被淘汰。
- 第 4 个位置的车手（技能为 5 的车手 4）击败了第 3 和第 5 个位置的车手（技能分别为 1, 3 的车手 3, 5），未被淘汰。
第 2 轮，车手列表为 $[1, 2, X, 4, X]$。
- 第 2 个位置的车手输给了第 1 和第 4 个位置的车手，被淘汰。
- 第 1 个位置的车手击败了第 2 个位置的车手，未被淘汰。
- 第 4 个位置的车手击败了其他两名车手，未被淘汰。
第 3 轮，车手列表为 $[1, X, X, 4, X]$。
- 第 1 个位置的车手输给了第 4 和第 4 个位置的车手（与自身是同一名车手），被淘汰。
- 第 4 个位置的车手击败了第 1 个位置的车手，未被淘汰。

因此： 第 1 个位置的车手在第 3 轮被淘汰。 第 2 个位置的车手在第 2 轮被淘汰。 第 3 个位置的车手在第 1 轮被淘汰。 第 4 个位置的车手赢得了比赛。 * 第 5 个位置的车手在第 1 轮被淘汰。

使得查询的回答为 $[3, 2, 1, 0, 1]$。

在第二场比赛中，车手按列表 $[1, 3, 5, 2, 4]$ 排列。比赛过程如下。

第 1 轮：
- 第 2 个位置的车手（技能为 1 的车手 3）输给了第 1 和第 3 个位置的车手（技能分别为 4, 3 的车手 1, 5），被淘汰。
- 第 4 个位置的车手（技能为 2 的车手 2）输给了第 3 和第 5 个位置的车手（技能分别为 3, 5 的车手 5, 4），被淘汰。
- 第 1 个位置的车手（技能为 4 的车手 1）击败了第 2 个位置的车手（技能为 1 的车手 3），未被淘汰。
- 第 3 个位置的车手（技能为 3 的车手 5）击败了第 2 和第 4 个位置的车手（技能分别为 1, 2 的车手 3, 2），未被淘汰。
- 第 5 个位置的车手（技能为 5 的车手 4）击败了第 4 和第 1 个位置的车手（技能分别为 2, 4 的车手 2, 1），未被淘汰。
第 2 轮，车手列表为 $[1, X, 5, X, 4]$。
- 第 3 个位置的车手输给了第 1 和第 5 个位置的车手，被淘汰。
- 第 1 个位置的车手击败了第 3 个位置的车手，未被淘汰。
- 第 5 个位置的车手击败了其他两名车手，未被淘汰。
第 3 轮，车手列表为 $[1, X, X, X, 4]$。
- 第 1 个位置的车手输给了第 5 和第 5 个位置的车手（与自身是同一名车手），被淘汰。
- 第 5 个位置的车手击败了第 1 个位置的车手，未被淘汰。

因此： 第 1 个位置的车手在第 3 轮被淘汰。 第 2 个位置的车手在第 1 轮被淘汰。 第 3 个位置的车手在第 2 轮被淘汰。 第 4 个位置的车手在第 1 轮被淘汰。 * 第 5 个位置的车手赢得了比赛。

使得查询的回答为 $[3, 1, 2, 1, 0]$。

QOJ.ac