题解：CF2031F Penchick and Even Medians

赛时坠机了，赛后把 F 做出来了。。

刚开始做不出来，后来注意到样例输出了长度为 n-2 的询问，启发我对于每个相邻数对 (i,i+1)，将其删去再进行询问，其中 i 为奇数，共消耗 50 次。然后我们对输出的两个数 x,y 进行讨论：

1. 如果 x,y 满足 x=\frac n 2,y=\frac n 2 +1，则说明删去的两个数其中一个数小于 \frac n 2，一个数大于 \frac n 2 +1。这种情况貌似对答案并不影响。

2. 如果 x,y 满足 x<\frac n 2,y > \frac n 2 + 1，则说明删除的数正是 \frac n 2 和 \frac n 2 +1，这种情况是好处理的。

3. 如果 x,y 满足 x=\frac n 2,y> \frac n 2+1，则说明 \frac n 2+1 正好在这个数对里面，将其记录下来。

4. 如果 x,y 满足 x<\frac n 2,y=\frac n 2+1，跟上面的情况类似。

5. 如果 x,y 满足 x<\frac n 2,y=\frac n 2，这种情况有些复杂，也是本题的重点，数对中的数都大于等于 \frac n 2+1。

6. 如果 x,y 满足 x=\frac n 2+1,y>\frac n 2+1，跟上面情况类似。

发现最麻烦的是第 5,6 类点对，我们把第 5 类点对存入一个数组，第 6 类存入另一个数组，现在考虑找到包含 \frac n 2 的点对和 \frac n 2 +1 的点对，怎么找呢？其实也是简单的，直接询问第一个数组的第一个点对与第二个数组的第一个点对，第一个数组的第二个点对与第二个数组的第二个点对......这样子只要结果输出了 \frac n 2 或 \frac n 2+1，我们就能够确定包含这两个数的两个点对了。

找到点对后怎么处理都行，算一下操作次数，首先要花 50 次枚举点对，然后再最多花 25 次找两个点对，最后花 4 次确定位置，总共 79 次，可以通过。

代码很丑，仅供参考：

   #include <bits/stdc++.h>
   #define rep(i, l, r) for (int i (l); i <= r; ++ i)
   #define rrp(i, l, r) for (int i (r); i >= l; -- i)
   #define pii pair <int, int>
   #define eb emplace_back
   #define inf 1000000000000
   using namespace std;
   constexpr int N = 100 + 5, K = 10;
   typedef unsigned long long ull;
   typedef long long ll;
   inline int rd () {
     int x = 0, f = 1;
     char ch = getchar ();
     while (! isdigit (ch)) {
       if (ch == '-') f = -1;
       ch = getchar ();
     }
     while (isdigit (ch)) {
       x = (x << 1) + (x << 3) + ch - 48;
       ch = getchar ();
     }
     return x * f;
   }
   int n;
   pii ask1 (int x, int y) {
     cout << "? " << n - 2 << " ";
     rep (i, 1, n) {
       if (i != x && i != y) cout << i << " ";
     }
     cout << endl;
     cin >> x >> y;
     return pii (x, y);
   }
   pii ask2 (int a, int b, int c, int d) {
     cout << "? 4 " << a << " " << b << " " << c << " " << d << endl; 
     int x, y;
     cin >> x >> y;
     return pii (x, y);
   }
   int a1[N], n1, a2[N], n2, tt;
   void motherfucker () {
     ++ tt;
     cin >> n; n1 = n2 = 0;
     int f1 = 0, f2 = 0;
     int x = 0, y = 0, z = 0;
     rep (i, 1, n) {
       pii t = ask1 (i, i + 1);
       if (t.first == n / 2 && t.second == n / 2 + 1) {
         if (! f1) f1 = i; else f2 = i;
       } else {
         if (t.first == n / 2 && t.second > n / 2 + 1) {
           y = i;
         } else 
         if (t.first < n / 2 && t.second == n / 2 + 1) {
           x = i;
         } else {
           if (t.first < n / 2 && t.second > n / 2 + 1) {
             z = i; ++ i; continue;
           }
           if (t.first < n / 2 && t.second == n / 2) a2[++ n2] = i;
           else a1[++ n1] = i;
         }
       }
       ++ i;
     }
     if (z) {
       if (! f1) {
         rep (i, 1, n1) f1 = a1[i];
         rep (i, 1, n2) f2 = a2[i];
       } else {
         if (! f2) {
           rep (i, 1, n1) f2 = a1[i];
           rep (i, 1, n2) f2 = a2[i];
         }
       }
       pii t = ask2 (f1, f1 + 1, f2, z);
       if (t.first == n / 2 || t.second == n / 2) {
         cout << "! " << z << " " << z + 1 << endl; 
       } else cout << "! " << z + 1 << " " << z << endl;
       return ;
     } else {
       int mn = min (n1, n2);
       int l = 0, r = 0;
       rep (i, 1, mn) {
         pii t = ask2 (a1[i], a1[i] + 1, a2[i], a2[i] + 1);
         if (t.first == n / 2 || t.second == n / 2) x = a1[i];
         else l = a1[i];
         if (t.first == n / 2 + 1 || t.second == n / 2 + 1) y = a2[i];
         else r = a2[i];
       }
       if (n2)
       rep (i, n2 + 1, n1) {
         pii t = ask2 (a1[i], a1[i] + 1, a2[1], a2[1] + 1);
         if (t.first == n / 2 || t.second == n / 2) x = a1[i];
         else l = a1[i];
         if (t.first == n / 2 + 1 || t.second == n / 2 + 1) y = a2[1];
         else r = a2[1];
       }
       if (n1)
       rep (i, n1 + 1, n2) {
         pii t = ask2 (a1[1], a1[1] + 1, a2[i], a2[i] + 1);
         if (t.first == n / 2 || t.second == n / 2) x = a1[1];
         else l = a1[1];
         if (t.first == n / 2 + 1 || t.second == n / 2 + 1) y = a2[i];
         else r = a2[i];
       }
       if (f1) l = f1, r = f1 + 1;
       if (! l) l = r + 1; if (! r) r = l + 1;
       pii t = ask2 (l, r, x, y);
       int ans1 = 0, ans2 = 0;
       if (t.first == n / 2 || t.second == n / 2) {
         ans1 = x;
       }
       if (t.first == n / 2 + 1 || t.second == n / 2 + 1) {
         ans2 = y;
       }
       t = ask2 (l, r, x + 1, y);
       if (t.first == n / 2 || t.second == n / 2) {
         ans1 = x + 1;
       }
       if (t.first == n / 2 + 1 || t.second == n / 2 + 1) {
         ans2 = y;
       }
       t = ask2 (l, r, x, y + 1);
       if (t.first == n / 2 || t.second == n / 2) {
         ans1 = x;
       }
       if (t.first == n / 2 + 1 || t.second == n / 2 + 1) {
         ans2 = y + 1;
       }
       t = ask2 (l, r, x + 1, y + 1);
       if (t.first == n / 2 || t.second == n / 2) {
         ans1 = x + 1;
       }
       if (t.first == n / 2 + 1 || t.second == n / 2 + 1) {
         ans2 = y + 1;
       }
       cout << "! " << ans1 << " " << ans2 << endl;
     }
   }
   int main () {
     // freopen ("1.in", "r", stdin);
     int T; cin >> T;
     for (; T; -- T) motherfucker ();
   }