Solution - Codeforces 2031F Penchick and Even Medians

飞快秒掉了，没报名痛失首杀，痛苦。

简略题解：

考虑先随机二元下标 \((x_0, y_0)\) 满足删去 \((x_0, y_0)\) 后查询的中位数还是 \(\frac{n}{2}, \frac{n}{2} + 1\)，那么这就说明 \(p_{x_0}, p_{y_0}\) 一定在中位数的两边。

那么还剩下的 \(n - 2\) 个下标两两配对成 \(\frac{n - 2}{2}\) 组。
然后每一组与 \((x_0, y_0)\) 一起问，注意到只要二元组里有中位数那么问出来的就必定带中位数（\(p_{x_0}, p_{y_0}\) 一定在中位数的两边，那么加入中位数肯定被夹在中间，不管另一个在哪都肯定还在）。

于是规模就缩小到的 \(2\) 个二元组了，每个二元组各存在一个中位数（可能只有 \(1\) 个二元组，但这个答案更简单，就是这个二元组。）
那么就只有 \(2\times 2 = 4\) 种情况，可以问出 \(3\) 种，都不是就是另一种（只是减掉了一次询问，看起来不是很必要（？））。

于是后面部分的询问次数就是 \(\frac{n - 3}{2} + 3 = \frac{n}{2} + 2\) 次，那么就留下了 \(78 - \frac{n}{2}\) 次操作。

注意到随机成功的概率就是 \(\frac{2(\frac{n}{2} - 1)^2}{n(n - 1)}\)，越小其实概率越低，但是越小的次数越多，算一下看起来就很能过.jpg。

跑了下 desmos，挂掉的概率 \(\le 8\times 10^{-9}\)，应该没啥问题。

#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;
}