题意
有一个 \(0 \sim n - 1\) 的排列 \(a_1 \dots a_n\)，有以下两种询问：
- 询问一个集合 \(S\)，交互库返回 \(\min_{x \in S} a_x + \operatorname{mex}_{x \in S} a_x\)。（这种询问最多 \(35\) 次）
- 询问一个集合 \(S\)， 交互库返回 \(\min_{x \in S} a_x - \operatorname{mex}_{x \in S}a_x\)。（这种询问最多 \(1\) 次）
你的目标是找出 \(0\) 的位置。
特殊性质 A
序列的前一半是偶数，后一半是奇数。
那么只需在前一半里面二分，如果一个区间里面包含 \(0\)，那么他的询问 1 一定返回 1。
解法
我们要意识到，询问 2 一定是用来区分 \(1\) 和 \(0\) 的。
但是没有特殊性质时，我们的询问 1 的值或许会一样。比如 1 0 和 2 这两个集合，返回的都是 \(2\)。所以我们的首要任务就是将 \(1\) 和 \(0\) 分到两个集合中。
确定性算法想不到，随机化算法出战。考虑随机打乱序列将其分成两个部分，如果其中一个部分的询问 1 为 \(1\)，此时表明 \(1\) 和 \(0\) 被分到了两个集合里，此时再用一次询问 2，即可区分 \(0\) 和 \(1\)。这边的期望询问次数为 \(2\)。
最后再在 \(0\) 的那个集合中二分就可以了。
询问次数 \(O(\log n) + O(1)\)。
Code
#include <bits/stdc++.h>
using namespace std;int n, ans;int query(int op, vector<int> &a, int l, int r){cout << "? " << op << ' ' << r - l + 1;for(int i = l; i <= r; i++) cout << ' ' << a[i];cout << endl;int res; cin >> res;return res;
}int main(){cin >> n;if(n == 1){cout << "! " << 1 << endl;return 0;}vector<int> a(n + 1, 0);for(int i = 1; i <= n; i++) a[i] = i;random_device rd;mt19937 g(rd());while(1){shuffle(a.begin() + 1, a.end(), g);if(query(1, a, 1, n / 2) == 1) break;}vector<int> v;if(query(2, a, 1, n / 2) == 1) v.assign(a.begin() + 1 + (n + 1) / 2, a.end());else v.assign(a.begin() + 1, a.begin() + 1 + n / 2);v.insert(v.begin(), 0);int l = 1, r = v.size() - 1;while(l <= r){int mid = (l + r) >> 1;if(query(1, v, l, mid) == 1){ans = v[mid];r = mid - 1;}else l = mid + 1;}cout << "! " << ans;return 0;
}