QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#226451#7510. Independent SetSolitaryDream#RE 1ms3396kbC++172.2kb2023-10-25 23:13:472023-10-25 23:13:48

Judging History

你现在查看的是最新测评结果

  • [2023-10-25 23:13:48]
  • 评测
  • 测评结果:RE
  • 用时:1ms
  • 内存:3396kb
  • [2023-10-25 23:13:47]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
int n;
vector<pii> ans;
int tot = 0;
vector<int> Ask(const vector<int> &a) {
    tot += a.size();
    assert(tot <= 176000);
    // if (tot > 176000) return vector<int>(a.size(), 0);
    vector<int> cnt(a.size());
    cout << "? " << a.size();
    for (auto x : a) cout << ' ' << x;
    cout << endl;
    fflush(stdout);
    for (int i = 0; i < (int)cnt.size(); ++i) cin >> cnt[i];
    return cnt;
}
mt19937 rd(1025);
typedef vector<int>::iterator vit;
inline void Process(vit pl, vit pr, const vector<int> &Q) {
    if (pl + 1 == pr) {
        // cerr << *pl << ' ' << Q.size() << " **\n";
        vector<int> que(Q);
        que.insert(que.begin(), *pl);
        vector<int> cnt = Ask(que);
        for (int i = 0; i < (int)Q.size(); ++i) {
            int k = cnt[i + 1];
            while (k--) ans.push_back({Q[i], *pl});
        }
        return;
    }
    vit pm = pl + (pr - pl) / 2;
    vector<int> q1(pl, pm), q2(pm, pr);
    q1.insert(q1.end(), Q.begin(), Q.end());
    q2.insert(q2.end(), Q.begin(), Q.end());
    vector<int> cnt1 = Ask(q1);
    vector<int> cnt2 = Ask(q2);
    vector<int> QL, QR;
    for (int i = 0; i < Q.size(); ++i) if (cnt1[i + (pm - pl)]) QL.push_back(Q[i]);
    for (int i = 0; i < Q.size(); ++i) if (cnt2[i + (pr - pm)]) QR.push_back(Q[i]);
    if (QL.size()) Process(pl, pm, QL);
    if (QR.size()) Process(pm, pr, QR);
}
inline void Solve(vector<int> a) {
    shuffle(a.begin(), a.end(), rd);
    vector<int> cnt = Ask(a);
    vector<int> P, Q;
    int n = cnt.size();
    for (int i = 0; i < n; ++i)
        (cnt[i] ? Q : P).push_back(a[i]);
    if (Q.size()) {
        Process(P.begin(), P.end(), Q);
        if (Q.size() > 1) Solve(Q);
    }
}
int main() {
    // ios::sync_with_stdio(0);
    // cin.tie(0);
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) a[i] = i + 1;
    for (int i = 1; i <= n; ++i) {
        int k = Ask({i, i})[1];
        while (k--) ans.push_back({i, i});
    }
    Solve(a);
    cout << "! " << ans.size();
    for (auto [x, y] : ans) cout << ' ' << x << ' ' << y;
    cout << endl;
    fflush(stdout);
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3396kb

input:

4
0 0
0 0
0 0
0 1
0 0 1 0
0 1
0 0 2
0 1
0 0
0 2
0 2

output:

? 2 1 1
? 2 2 2
? 2 3 3
? 2 4 4
? 4 3 4 1 2
? 2 3 1
? 3 4 2 1
? 2 3 1
? 2 4 1
? 2 2 1
? 2 2 1
! 4 4 4 1 3 1 2 1 2

result:

ok Ok, Accepted!

Test #2:

score: -100
Runtime Error

input:

4000
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0...

output:

? 2 1 1
? 2 2 2
? 2 3 3
? 2 4 4
? 2 5 5
? 2 6 6
? 2 7 7
? 2 8 8
? 2 9 9
? 2 10 10
? 2 11 11
? 2 12 12
? 2 13 13
? 2 14 14
? 2 15 15
? 2 16 16
? 2 17 17
? 2 18 18
? 2 19 19
? 2 20 20
? 2 21 21
? 2 22 22
? 2 23 23
? 2 24 24
? 2 25 25
? 2 26 26
? 2 27 27
? 2 28 28
? 2 29 29
? 2 30 30
? 2 31 31
? 2 32 3...

result: