Problem Description

The EGOI closing ceremony is coming soon, and there will be $N$ important guests attending. They must sit in a single row according to a very strict diplomatic protocol. To determine the correct seating order, Noemi stayed up for two nights.

Veronica is in charge of the closing ceremony. She must make sure that the nameplates on the front-row seats are correct. But there is a small problem: Noemi did not tell her the correct seating order, and she cannot be found. Fortunately, the photographer Dorka has an app that can help.

Dorka needs to adjust her camera to take specific photos of the front-row guests. To tune her equipment, she needs to know how wide each photo must be, so Noemi wrote an app for her that can quickly output the information she needs. Veronica now wants to use this app to figure out the correct seating plan.

The $N$ important guests are numbered from $0$ to $N-1$. The front-row seats are also numbered from left to right as $0$ to $N-1$. For each $I$ ($0 \leq I \leq N-1$), $g_I$ denotes the guest number sitting in seat $I$, and $s_I$ denotes the seat number where guest $I$ should sit.

:::align{center}

A row of five guests. For this row, $g = [3, 1, 0, 2, 4]$ and $s = [2, 1, 3, 0, 4]$. :::

The app works as follows:

• Dorka enters the numbers $I$, $J$, $K$ of three different guests.
• The app tells her the minimum number of guests that must appear in a photo if she insists on having all three guests in the picture. Formally, the app displays the value $\max(s_I, s_J, s_K) - \min(s_I, s_J, s_K) + 1$.

For example, look at Figure 1:

• Guests $I=0$, $J=2$, and $K=4$ sit at positions $s_I = 2$, $s_J = 3$, and $s_K = 4$. If Dorka selects them, the app displays $\max(2,3,4) - \min(2,3,4) + 1 = 3$.

  In other words, the narrowest photo containing guests $0$, $2$, and $4$ contains exactly these three guests.

• Guests $I=0$, $J=4$, and $K=3$ sit at positions $s_I = 2$, $s_J = 4$, and $s_K = 0$. If Dorka selects them, the app displays $\max(2,4,0) - \min(2,4,0) + 1 = 5$.

  In other words, a photo containing these three guests must cover all $5$ guests.

Help Veronica use Dorka’s app to find the correct seating order. More precisely, your program must determine and output the sequence $g_0, g_1, \dots, g_{N-1}$. There are exactly two correct answers (one is the reverse of the other), and you may output either of them. Your score depends on the number of queries you make to the app.

Implementation Details

This is an interactive problem. Your program will interact with the grader via standard input and output, as described below.

Your program should first read a line containing a positive integer $T$, the number of test cases.

For each test case, your program should first read a line containing a positive integer $N$, the number of seats (and also the number of guests).

To make a query, your program should output a line of the form "? $I$ $J$ $K$", where $0 \leq I, J, K \leq N - 1$ are three distinct numbers.

After making a query, your program should read a line containing one positive integer, the answer to the query.

To output the correct seating order, your program should output a line of the form "! $g_0$ ... $g_{N-1}$".

After processing all $T$ test cases, your program should terminate normally.

Please note that the official grader used in CMS may be adaptive. This means that, for some test cases, the guests’ order is not fixed in advance. Instead, the grader may decide which remaining permutation to use based on the queries your program has already asked.

Flush the buffer. If you are not using the provided templates, make sure to flush standard output after printing each line, otherwise your program may be judged Not correct. In Python, if you read lines using input(), this will be done automatically; you can use print(..., flush=True) to force flushing. In C++, cout << endl; prints a newline and also flushes; if you use printf, use fflush(stdout).

1
5

3

3

5

? 0 2 4

? 3 0 1

? 0 4 3

! 3 1 0 2 4

Hint

Constraints

• $1 \leq T \leq 10$.
• $N$ is $5$ (only the sample), $8$, $40$, or $2000$.
• For each test case, you may make at most $10\ 000$ queries.

Scoring

Your program will be tested on testdata split into several subtasks. To get the score for a subtask, you must solve all test cases in that subtask correctly.

• Subtask $0$ [$0$ points]: Sample ($N = 5$).
• Subtask $1$ [$9$ points]: $N = 8$.
• Subtask $2$ [$11$ points]: $N = 2000$, and guests $0$ and $1$ sit next to each other.
• Subtask $3$ [$15$ points]: $N = 40$.
• Subtask $4$ [$65$ points]: $N = 2000$.

For subtasks 1 and 2, any solution that correctly solves all test cases will receive full points.

For subtasks 3 and 4, your solution must correctly solve all test cases to receive any points, and your score depends on $Q_s$, the maximum number of queries you need to solve one test case. Let $X_s = max( 1, Q_s / N )$. The scores for subtasks 3 and 4 are computed as follows:

For each subtask, the value $score_s$ is rounded to the nearest integer, and the total score is the sum of the subtask scores. To achieve full score, you need to use at most 55 queries in subtask 3, and at most 2597 queries in subtask 4. Sample values of $Q_s$ for subtasks 3 and 4 and the corresponding scores are shown in the table below.

:::align{center} :::

Sample Explanation

The sample input contains one test case ($T = 1$) with $N = 5$ guests. The hidden guest configuration in this test case corresponds to Figure 1.

The program’s first query is 0, 2, 4. The answer 3 tells us that these guests are seated in three adjacent seats in some unknown order.

The answer 3 to the second query tells us that the same is true for guests 3, 0, and 1.

We can now deduce that guest 0 must be seated in the middle, with guests 2 and 4 on one side, and guests 1 and 3 on the other side.

After the third query, we have determined that the guests must be seated in the order $[3, 1, 0, 2, 4]$ or in the reverse order $[4, 2, 0, 1, 3]$. We may output either of these.

Code Templates and Evaluation Details

We strongly recommend using the provided C++ and Python code templates. These templates check whether the interaction with the grader is successful, and terminate the program gracefully if the interaction fails.

The grader that interacts with your program will report an error and then terminate upon the first mistake. If you do not use the provided templates, this may cause your program to crash or wait forever for a response.

We also recommend using the testing tool (see below) for local testing before submission. The testing tool checks your program’s output and reports protocol violations.

Testing Tool

To make it easier to test your program, we provide a simple tool that you can download. This tool is optional. Note that the grader used by Luogu is different from the testing tool.

To use the tool, you need an input file. You may use the provided sample input seatingplan.input0.txt, or create your own. The input file should start with a line containing the number of test cases $T$, then each test case uses two lines: one line with $N$, and one line with $g_0, g_1, ..., g_{N-1}$.

For a Python program, assuming it is seatingplan.py (usually run as pypy3 seatingplan.py), run the testing tool as follows:

    python3 testing_tool.py pypy3 seatingplan.py < seatingplan.input0.txt

For a C++ program, first compile your program:

    g++ -DEVAL -std=gnu++20 -O2 -pipe -static -s -o seatingplan seatingplan.cpp

Then run the testing tool:

    python3 testing_tool.py ./seatingplan < seatingplan.input0.txt

Translated by ChatGPT 5