QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#226451 | #7510. Independent Set | SolitaryDream# | RE | 1ms | 3396kb | C++17 | 2.2kb | 2023-10-25 23:13:47 | 2023-10-25 23:13:48 |
Judging History
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;
}
詳細信息
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...