Median Queries

题意翻译

**本题是一道交互题。** 给定 $n$，你需要猜测一个长度为 $n$ 的排列 $p$（即 $p$ 包含所有 $1$ 到 $n$ 的整数各一次）。已知 $p$ 满足 $p_1<p_2$。 当然，你可以进行询问，每次询问你需要给定三个互不相同的整数 $a,b,c$，交互器会返回 $|p_a-p_b|,|p_b-p_c|,|p_c-p_a|$ 这三个数中第二小的数。 请在 $2\times n+420$ 次询问内求出整个排列 $p$。$T$ 组数据。 交互格式如下： - 首先你需要读入整数 $T$ 表示数据组数。接下来对于每组数据： - 首先读入一个整数 $n$ 表示排列长度。如果你希望询问，按照 `? a b c` 的格式输出，你将收到 $|p_a-p_b|,|p_b-p_c|,|p_c-p_a|$ 中第二小的数。你需要保证 $1\leq a,b,c\leq n$，且 $a,b,c$ 互不相同。请注意，如果你的询问不合法，或者你的询问次数过多，交互器会给出 `-1` 的结果，此时你需要立即停止程序，否则可能会得到任意的评测结果。如果你希望回答，按照 `! p_1 p_2 ... p_n` 的格式输出。如果你的回答正确，交互器会给出 `1` 的结果，此时你需要直接进行下一组数据（如果有的话），否则交互器会给出 `-1` 的结果，同样的你需要立刻结束程序。 注意刷新缓冲区。 $1\leq T\leq10^3;20\leq n,\sum n\leq10^5;$

题目描述

This is an interactive problem. There is a secret permutation $ p $ ( $ 1 $ -indexed) of numbers from $ 1 $ to $ n $ . More formally, for $ 1 \leq i \leq n $ , $ 1 \leq p[i] \leq n $ and for $ 1 \leq i < j \leq n $ , $ p[i] \neq p[j] $ . It is known that $ p[1]<p[2] $ . In $ 1 $ query, you give $ 3 $ distinct integers $ a,b,c $ ( $ 1 \leq a,b,c \leq n $ ), and receive the median of $ \{|p[a]-p|,|p-p[c]|,|p[a]-p[c]|\} $ . In this case, the median is the $ 2 $ -nd element ( $ 1 $ -indexed) of the sequence when sorted in non-decreasing order. The median of $ \{4,6,2\} $ is $ 4 $ and the median of $ \{0,123,33\} $ is $ 33 $ . Can you find the secret permutation in not more than $ 2n+420 $ queries? Note: the grader is not adaptive: the permutation is fixed before any queries are made.

输入输出格式

输入格式

The first line of input contains a single integer $ t $ $ (1 \leq t \leq 1000) $ — the number of testcases. The first line of each testcase consists of a single integer $ n $ $ (20 \leq n \leq 100000) $ — the length of the secret permutation. It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 100000 $ .

输出格式

For each testcase, you begin the interaction by reading $ n $ . To perform a query, output "? a b c" where $ a,b,c $ is the $ 3 $ indices you want to use for the query. Numbers have to satisfy $ 1 \leq a,b,c \leq n $ and $ a \neq b $ , $ b \neq c $ , $ a \neq c $ . For each query, you will receive a single integer $ x $ : the median of $ \{|p[a]-p|,|p-p[c]|,|p[a]-p[c]|\} $ . In case your query is invalid or you asked more than $ 2n+420 $ queries, the interactor will print "−1" and will finish interaction. You will receive Wrong answer verdict. Make sure to exit immediately to avoid getting other verdicts. When you have determined the secret permutation, output "! p\[1\] p\[2\] ... p\[n\]". If the secret permutation is correct, the interactor will print "1". Otherwise, the interactor will print "-1" and will finish interaction. You will receive Wrong answer verdict. Make sure to exit immediately to avoid getting other verdicts. After printing a query do not forget to output the end of line and flush the output. Otherwise, you will get Idleness limit exceeded verdict. To do this, use: - fflush(stdout) or cout.flush() in C++; - System.out.flush() in Java; - flush(output) in Pascal; - stdout.flush() in Python; - see documentation for other languages. Hacks: To hack, use the following format of test: The first line should contain a single integer $ t $ ( $ 1 \leq t \leq 1000 $ ) — the number of testcases. The first line of each testcase should contain a single integer $ n $ ( $ 20 \leq n \leq 100000 $ ) — the length of the secret permutation. The following line of should contain $ n $ integers $ p[1],p[2],p[3],\ldots,p[n] $ . $ p[1]<p[2] $ and $ p $ must be a permutation of integers from $ 1 $ to $ n $ . You must ensure that the sum of $ n $ over all testcases does not exceed $ 100000 $ .

输入输出样例

输入样例 #1

1
20

6

9

1

输出样例 #1

? 1 5 2

? 20 19 2

! 9 10 19 7 16 18 11 14 15 6 20 8 17 4 5 3 12 2 13 1

说明

The secret permutation is $ \{9,10,19,7,16,18,11,14,15,6,20,8,17,4,5,3,12,2,13,1\} $ . For the first query, the values of $ (a,b,c) $ is $ (1,5,2) $ . Since $ p[1]=9 $ , $ p[5]=16 $ and $ p[2]=10 $ . The return value is the median of $ \{|9-16|,|16-10|,|9-10|\} $ which is $ 6 $ . For the second query, the values of $ (a,b,c) $ is $ (20,19,2) $ . Since $ p[20]=1 $ , $ p[19]=13 $ and $ p[2]=10 $ . The return value is the median of $ \{|1-13|,|13-10|,|1-10|\} $ which is $ 9 $ . By some miracle, we have figured out that the secret permutation is $ \{9,10,19,7,16,18,11,14,15,6,20,8,17,4,5,3,12,2,13,1\} $ . We output it and receive $ 1 $ from the interactor, meaning that we have guessed the secret permutation correctly.