CF987 Div2 F 题解

阶段 1

考虑我们每次随机删除两个然后询问，若中位数为 \(\frac{n}{2}, \frac{n}{2} + 1\) 称被删除的两个为基准数，用 \(v_1, v_2\) 代表。每次询问得到解的概率约为 \(\frac{1}{2}\)。

发现基准数一定一个 \(< \frac{n}{2}\) 一个 \(> \frac{n}{2} + 1\)，且对于一次四个数的询问 \(x_1, x_2, v_1, v_2\)，若 \(x_1, x_2\) 中有 \(\frac{n}{2}\) 或 \(\frac{n}{2} + 1\) 则一定会被返回在 \(m_1, m_2\) 中。

阶段 2

两个两个依次询问 \(\le \frac{n}{2}\) 次确认即可得到答案所在的位置（4 个位置或者 2 个位置），再对它们进行 \(O(1)\) 次询问确认真正的位置即可。

正确率约为 \((1 - 2^{-30})\)。

更进一步

在阶段 1 我们可能可以分讨使得接下来的次数减少，可能可以得到更高的正确率或者确定性做法。