C. Nastia and a Hidden Permutation

传送门

题解

第一次做交互题，有意思的一个题。

题目大意是Nastia有一个由1到n组成的排列，你需要通过两种询问方式用最多\(\lfloor \frac{3\cdot n}{2} \rfloor + 30 \)次询问来确定这个排列，你的每次询问Nastia会给你一个回答。

首先我们可以通过\(log_2(n)\)次的询问来确定排列中的第i个值，令i=1，也就是通过\(log_2(n)\)次询问确定\(p_1 \)。这\(log_2(n)\)次询问都通过第二种方式询问，即询问样式可以为"? 2 1 2 x"，如果回答的数为x，那么说明\(p_1 \leq x\)，这样我们可以通过二分找到\(p_1 \)的值。有了排列中的一个值，其余的n-1个值每个我们最多2次询问就可以确定其值。

假设\(p_1 > \lfloor \frac{n}{2} \rfloor \)，对于i的值，则我们第一次询问可以确定\(p_i \)和\(p_1 \)的大小关系。询问格式为"? 2 i 1 1"，这个询问只有两种结果\(p_1 \)和\(p_i \)。因为\(p_1 > \lfloor \frac{n}{2} \rfloor \)，所以\(p_1 > 1 \)，所以\(max(1, p_i)=p_i, max(2, p_1)=p_1 \)，所以\(min(max(1, p_i), max(2, p_1))=min(p_i, p_1)\)，所以通过一次询问可以确定\(p_i \)和\(p_1 \)的大小关系，如果询问的结果不是\(p_1\)，即\(min(p_i, p_1) \neq p_1\)，就可以直接确定\(p_i\)为返回的结果。否则，\(p_i > p_1\)，进行第二次询问，询问格式为"? 1 1 i n-1"。通过第一次询问我们确定了\(p_i > p_1\)，所以\(p_1 < n, min(n-1, p_1)=p_1, min(n, p_i)=p_i\)，所以\(max(min(n-1, p_1), min(n, p_i))=max(p_1, p_i)=p_i\)，第二次询问确定\(p_i\)的值。

假设\(p_1 \leq \lfloor \frac{n}{2} \rfloor \)，对于i的值，则我们第一次询问可以确定\(p_i \)和\(p_1 \)的大小关系。询问格式为"? 1 1 i n-1"，这个询问只有两种结果\(p_1 \)和\(p_i \)。因为\(p_1 \leq \lfloor \frac{n}{2} \rfloor \)，所以\(p_1 < n \)，所以\(min(n-1, p_1)=p_1\)，\(min(n, p_i)=p_i \)，所以\(max(min(n-1, p_1), min(n, p_i))=max(p_1, p_i)\)，所以通过一次询问可以确定\(p_i \)和\(p_1 \)的大小关系，如果询问的结果不是\(p_1\)，即\(max(p_1, p_i) \neq p_1\)，就可以直接确定\(p_i\)为返回的结果。否则，\(p_i < p_1\)，进行第二次询问，询问格式为"? 2 i 1 1"。通过第一次询问我们确定了\(p_i < p_1\)，所以\(p_1 > 1, max(1, p_i)=p_i, max(2, p_1)=p_1\)，所以\(min(max(1, p_i), min(2, p_1))=min(p_i, p_1)=p_i\)，第二次询问确定\(p_i\)的值。

思考：为什么要分开讨论\(p_1 > \lfloor \frac{n}{2} \rfloor \)和\(p_1 \leq \lfloor \frac{n}{2} \rfloor \) ？

分开讨论\(p_1 > \lfloor \frac{n}{2} \rfloor \)和\(p_1 \leq \lfloor \frac{n}{2} \rfloor \)可以保证的询问不超过\(\lfloor \frac{3\cdot n}{2} \rfloor + 30 \)次。分开讨论的话，如果\(p_1 > \lfloor \frac{n}{2} \rfloor \)，对于所有的小于\(p_1\)的\(p_i\)可以一次询问确定其值，对于大于\(p_1\)的\(p_i\)需要询问2次，总计需要\(log_2(n)+p_1-1+2*(n-p_1)\)次询问确定排列，\(log_2(n)+p_1-1+2*(n-p_1)=log_2(n)+2*n-1-p_1\)，这是个单调递减函数，最大时\(p_1\)取值\(\lfloor \frac{n}{2}\rfloor+1\)，函数值为\(log_2(n)+\frac{3\cdot n}{2}-2\)。同理，如果\(p_1 \leq \lfloor \frac{n}{2} \rfloor \)，需要\(log_2(n)+2*(p_1-1)+n-p_1=log_2(n)+p_1+n-1\)次询问确定排列，这是个单调递增函数，取最大值时\(p_1\)取值\(\lfloor \frac{n}{2} \rfloor\)，最大值为\(log_2(n)+\frac{3\cdot n}{2}-1\)。

代码