P14828 彻彻崩 题解

namespace lowspeed_song {

inline void init() {
}

int l[510], r[510], best[510], res[510];

inline void sol([[maybe_unused]]int __testcase_id) {
    int n; cin >> n;
    mt19937 mt(time(0));
    for (int i = 1; i <= n; ++i) l[i] = 1, r[i] = n, best[i] = n;
    while (1) {
        vector<int> used, ord(n + 1);
        vector<pair<int, int>> queries;
        iota(ord.begin(), ord.end(), 0);
        shuffle(ord.begin() + 1, ord.end(), mt);
        for (int i = 1; i <= n; ++i) if (l[ord[i]] <= r[ord[i]]) {
            int mid = l[ord[i]] + r[ord[i]] >> 1, more = (mid - l[ord[i]] + 1) * (1 << used.size());
            if (more + queries.size() <= n * 20) {
                for (int j = l[ord[i]]; j <= mid; ++j)
                    for (int k = 0; k < (1 << used.size()); ++k)
                        queries.emplace_back(j, ord[i]);
                used.emplace_back(ord[i]);
            }
        }
        if (queries.empty()) break;
        cout << "? " << queries.size() << ' ';
        for (auto &[i, j] : queries) cout << i << ' ' << j << ' '; cout << endl;
        int repo; cin >> repo;
        for (int i = 0; i < used.size(); ++i)
            if (repo >> i & 1) {
                int mid = l[used[i]] + r[used[i]] >> 1;
                best[used[i]] = mid, r[used[i]] = mid - 1;
            } else {
                int mid = l[used[i]] + r[used[i]] >> 1;
                l[used[i]] = mid + 1;
            }
    }
    for (int i = 1; i <= n; ++i) res[best[i]] = i;
    cout << "! ";
    for (int i = 1; i <= n; ++i) cout << res[i] << ' ';
    cout << endl;
}

} // namespace lowspeed_song