CF1526F Median Queries

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]

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[b]|,|p[b]-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]

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.