本题是一道交互题。
有一个长度为 $n$ 的排列，你有两种询问：
- $\max(\min(x,p_i),\min(x+1,p_j))$。
- $\min(\max(x,p_i),\max(x+1,p_j)$。
其中 $x,i,j$ 由你决定，需要满足 $i\not=j,1\le x\le n-1$。
你可以做出最多 $\lfloor\frac{3n}{2}\rfloor+30$ 次询问，并确定这个排列每个位置上的数。
共有 $t$ 组数据。
$1\le t\le10^4,3\le n\le 10^4,\sum n\le2\times10^4$。
一道蛮有意思的交互。
根据套路，我们先尝试找出 $1$，然后再推出整个排列。
考虑把询问中的一些东西定下来，只剩下我们想知道的东西。
我们使用操作 $2$，并令 $x=1$，这样第一个 $\max$ 就一定等于 $p_i$，第二个 $\max$ 就等于 $\max(2,p_j)$。
显然第二个 $\max\ge2$，于是返回值为 $1$ 当且仅当 $p_i=1$。
那我们随便固定一个 $j$，枚举 $i$，用 $n-1$ 次询问即可找出 $p_i=1$ 的位置。
那剩下的部分就很简单了，直接枚举 $j$，查询 $\max(\min(1,1),\min(2,p_j))$，返回值一定是 $p_j$，这里又用了 $n-1$ 次询问。
观察到限制是 $\frac{3n}{2}=n+\frac{n}{2}$，显然后半部分的操作无法省略，于是我们要把前半部分的询问次数减半。
注意到前半部分的询问中，$j$ 这个位置我们没有用到，再结合减半的目标，容易想到把整个序列两两分组询问。
我们再看一次询问 $\min(\max(1,p_i),\max(2,p_j))$ 能得出的结果：
- 结果为 $1$，则 $p_i=1$。
- 结果 $>2$，那 $p_i,p_j\not=1$。
- 结果为 $2$，可以得到 $p_i\not=1,p_j=1/2$。
最坏情况下每次排除两个数，并且遇到了第三种情况且 $p_j=1/2$，分别再多消耗一次询问确定 $p_j$ 是否为 $1$，此时的询问次数为 $\lfloor\frac{n}{2}\rfloor+2$，即可通过本题。
$code$
1 |
|