題意

有一個 \(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;
}