F. Median Queries
constructive algorithms; interactive; probabilities
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[b]|,|p[b]-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\).
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.