Codeforces Round #720 Nastia and a Hidden Permutation

题意

这又是一道交互式的题目。

Nastia有一个1-n的排列。现在每次你可以做两种查询

要求最多做$\lfloor \frac {3 \cdot n} { 2} \rfloor + 30$次查询。要你输出原排列。

如果对于第一种查询，我们每次x都取n-1。对于第二种查询我们每次x都取1。
于是对于$p_i$和$p_j$不等于1或2或n-1或n的时候，第一种查询等价为：$\max{(p_i, p_j)}$。第二种查询等价为：$\min{(p_i, p_j)}$。

于是，在大多数情况下，在上述两个查询的基础上，我们可以通过新增下列查询得出$p_i$和$p_j$的值：$$min{(\max{(x, p_i)}, \max{(x + 1, p_j)})}，其中x=\min{(p_i, p_j)}$$

对于第三种查询：由于$x=\min{(p_i, p_j)}$，因此当且仅当$p_j>p_i=x=\min{(p_i, p_j)}$时，$min{(\max{(x, p_i)}, \max{(x + 1, p_j)})}=\min{(p_i, p_j)}=x=p_i$。

于是我们通过第三个查询就能得出两个数当中较小的那个数的位置，进而也就确定了较大的数的位置。

然后我们再来对$p_i$和$p_j$等于1或2或n-1或n的情况进行处理。

不难发现，$\min{(\max{(1, p_i)}, \max{(2, p_j)})}=1$时，$p_i$必为1。但这种情况其实恰好和一般情况的处理方式一致。

那么当$\min{(\max{(1, p_i)}, \max{(2, p_j)})}=2$时，我们首先怀疑$p_j$是否等于1。于是我们调换i,j的位置，再查一次。如果$p_j$不是1，那么其实结论和一般情况等价。

综上我们所需要做的工作就只是在$\min{(\max{(1, p_i)}, \max{(2, p_j)})}=2$且$\min{(\max{(1, p_j)}, \max{(2, p_i)})}=1$时，修正把一般情况的$p_j=2$修正成$p_j=1$即可。

同理，$\max{(\min{(n-1, p_i)}, \min{(n, p_j)})}=n-1$且$\max{(\min{(n-1, p_j)}, \min{(n, p_i)})}=n$时，修正$p_i$的值为n即可。