Codeforces Round #720 Nastia and a Hidden Permutation - 模拟

题意

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

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

  1. 给他一个i,j和x。他给你$\max{(\min{(x, p_i)}, \min{(x + 1, p_j)})}$
  2. 给他一个i,j和x。他给你$\min{(\max{(x, p_i)}, \max{(x + 1, p_j)})}$

要求最多做$\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即可。


代码

Submission #115626975 - Codeforces
Codeforces. Programming competitions and contests, programming community