自行車競賽 - 题目

有 $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
>>> 5
? 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

在範例中，選手的技能值分別為 $4, 2, 1, 5, 3$。

在舉辦的第一場比賽中，選手被排列成列表 $[1, 2, 3, 4, 5]$。比賽進行如下；每一輪中，選手列表顯示如下，其中被淘汰的選手以 $X$ 取代。

第 1 輪：
- 第 3 個位置的選手（選手 3，技能值 1）輸給了第 2 和第 4 個位置的選手（選手 2, 4，技能值 2, 5），被淘汰。
- 第 5 個位置的選手（選手 5，技能值 3）輸給了第 4 和第 1 個位置的選手（選手 4, 1，技能值 5, 4），被淘汰。
- 第 1 個位置的選手（選手 1，技能值 4）擊敗了第 5 和第 2 個位置的選手（選手 5, 2，技能值 3, 2），因此未被淘汰。
- 第 2 個位置的選手（選手 2，技能值 2）擊敗了第 3 個位置的選手（選手 3，技能值 1），因此未被淘汰。
- 第 4 個位置的選手（選手 4，技能值 5）擊敗了第 3 和第 5 個位置的選手（選手 3, 5，技能值 1, 3），因此未被淘汰。
第 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 個位置的選手（選手 3，技能值 1）輸給了第 1 和第 3 個位置的選手（選手 1, 5，技能值 4, 3），被淘汰。
- 第 4 個位置的選手（選手 2，技能值 2）輸給了第 3 和第 5 個位置的選手（選手 5, 4，技能值 3, 5），被淘汰。
- 第 1 個位置的選手（選手 1，技能值 4）擊敗了第 2 個位置的選手（選手 3，技能值 1），因此未被淘汰。
- 第 3 個位置的選手（選手 5，技能值 3）擊敗了第 2 和第 4 個位置的選手（選手 3, 2，技能值 1, 2），因此未被淘汰。
- 第 5 個位置的選手（選手 4，技能值 5）擊敗了第 4 和第 1 個位置的選手（選手 2, 1，技能值 2, 4），因此未被淘汰。
第 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