Codeforces 2031F Penchick and Even Medians

我的博客。

首先因为 n 就为偶数，中位数就是 (\frac{n}{2}, \frac{n}{2} + 1)。

考虑到 n\le 100，q\le 80，所以第一想法是尝试去排除一些无用的状态。
那么因为长度为偶数，所以只能通过两个两个删来判断。

但是手玩一下发现这样做好像没啥前途。
但是手玩的过程中能知道，如果删去的两个下标 x, y 满足 p_x, p_y 一个 < \frac{n}{2}，一个 > \frac{n}{2} + 1，那么查询出来的一定还是 (\frac{n}{2}, \frac{n}{2} + 1)。

令这个对为 (x_0, y_0)，那么就会发现这个 x_0, y_0 是容易判断的，看起来也有点用，于是考虑利用一下这个对（关于如何求出 (x_0, y_0)，放到下面再探讨）。

那么一个想法就是让询问中包含 x_0, y_0 两个下标。
又因为询问必须为偶数，所以将剩下 n - 2 个下标随意两两配对，记为 (x_i, y_i)。
那么去询问 (x_0, y_0, x_i, y_i)，考虑这会有什么性质。
（为什么是两两配对一次只问 4 个？因为询问的越多得到的信息就相对越模糊。）

注意到，如果 p_{x_i}, p_{y_i} 中含有 \frac{n}{2}, \frac{n}{2} + 1，那么返回的值就必然带有这些数。
这是因为 p_{x_0}, p_{y_0} 在 \frac{n}{2}, \frac{n}{2} + 1 的两边，所以当 \frac{n}{2} 或者 \frac{n}{2} + 1 放进去的时候必然会被两个数夹在中间，那么不管另一个数是什么肯定都不会影响返回的中位数带有 \frac{n}{2} 或者 \frac{n}{2} + 1。

否则，如果 p_{x_i}, p_{y_i} 中不含有 \frac{n}{2}, \frac{n}{2} + 1，那么返回的值必没有这些数。
这是比较显然的，因为都没有这些数就不可能带这些数了。

于是考虑把每一对都询问下来后留下询问的返回值中带有 \frac{n}{2} 或者 \frac{n}{2} + 1 的下标对 (x_1, y_1), (x_2, y_2)，那么可以知道的是 \frac{n}{2} 和 \frac{n}{2} + 1 必出现在这两对的下标之中，且每对都恰好只有 1 个对应的下标。
那么实际上就只有 2\times 2 = 4 种情况，可以直接枚举每一对选出的下标 a, b，如果询问 (x_0, y_0, a, b) 为 (\frac{n}{2}, \frac{n}{2} + 1)，那么答案就为 (a, b)。
如果想的话也可以优化掉 1 次操作：枚举 3 种，都不合法就为剩下的一种。这个优化实际上并不必要，想加就加。

其实还有一种情况是问出来的对只有一个 (x_1, y_1)，但是这个时候答案肯定就为 (x_1, y_1)，更为简单。

那么可以知道的是，只要知道了 (x_0, y_0)，只需要 \frac{n - 2}{2} + 3 = \frac{n}{2} + 2 次询问就可以得到答案了。

于是现在的问题来到了在 78 - \frac{n}{2} 次询问内得到一组合法的 (x_0, y_0)。

注意到 p_{x_0}, p_{y_0} 只需要满足一个 < \frac{n}{2} 一个 > \frac{n}{2} + 1 就合法了，那么合法的 p_{x_0}, p_{y_0} 的数量应该挺多的，且题目并没有交互库自适应。
所以可以考虑随机化得出 (x_0, y_0)，至于判断，方法在一开始就已经提到了。

随出合法下标对的概率分析：
单次随出合法的概率就为 \frac{2(\frac{n}{2} - 1)^2}{n(n - 1)}，那么总失败率就为 (1 - \frac{2(\frac{n}{2} - 1)^2}{n(n - 1)})^{78 - \frac{n}{2}}。
放到 desmos 里面观察，当 n = 100 时取到失败率最大值，约为 8.5\times 10^{-9}，非常可过阿。

代码优化了最后 1 次询问，写的好像有点丑了 qaq。

#include<bits/stdc++.h>
std::mt19937_64 eng(std::chrono::steady_clock::now().time_since_epoch().count());
constexpr int maxn = 1e2 + 10;
std::pair<int, int> query(std::vector<int> a) {
   std::cout << "? " << a.size();
   for (int x : a) std::cout << ' ' << x;
   std::cout << std::endl;
   int x, y;
   std::cin >> x >> y;
   return std::make_pair(x, y);
}
inline void solve() {
   int n;
   std::cin >> n;
   int x0 = 0, y0 = 0;
   do {
      int x = eng() % n + 1, y;
      do {
         y = eng() % n + 1;
      } while (y == x);
      std::vector<int> vec;
      for (int i = 1; i <= n; i++) {
         if (i == x || i == y) continue;
         vec.push_back(i);
      }
      if (query(vec) == std::make_pair(n / 2, n / 2 + 1)) {
         x0 = x, y0 = y;
      }
   } while (! x0);
   std::pair<int, int> c[2] = {{0, 0}, {0, 0}};
   for (int i = 1, j = 0, k = 0; i <= n; i++) {
      if (i == x0 || i == y0) continue;
      if (j) {
         auto [x, y] = query({i, j, x0, y0});
         if (x == n / 2 || x == n / 2 + 1 || y == n / 2 || y == n / 2 + 1) {
            c[k++] = {i, j};
         }
         j = 0;
      } else {
         j = i;
      }
   }
   if (! c[1].first) {
      std::cout << "! " << c[0].first << ' ' << c[0].second << std::endl;
   } else if (query({c[0].first, c[1].first, x0, y0}) == std::make_pair(n / 2, n / 2 + 1)) {
      std::cout << "! " << c[0].first << ' ' << c[1].first << std::endl;
   } else if (query({c[0].first, c[1].second, x0, y0}) == std::make_pair(n / 2, n / 2 + 1)) {
      std::cout << "! " << c[0].first << ' ' << c[1].second << std::endl;
   } else if (query({c[0].second, c[1].first, x0, y0}) == std::make_pair(n / 2, n / 2 + 1)) {
      std::cout << "! " << c[0].second << ' ' << c[1].first << std::endl;
   } else {
      std::cout << "! " << c[0].second << ' ' << c[1].second << std::endl;
   }
}
int main() {
   int T;
   for (std::cin >> T; T--; ) {
      solve();
   }
   return 0;
}