QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#188883 | #7510. Independent Set | zhoukangyang# | TL | 0ms | 0kb | C++11 | 2.9kb | 2023-09-26 16:07:39 | 2023-09-26 16:07:39 |
answer
#include<bits/stdc++.h>
#define L(i, j, k) for(int i = (j); i <= (k); ++i)
#define R(i, j, k) for(int i = (j); i >= (k); --i)
#define ll long long
#define vi vector < int >
#define sz(a) ((int) (a).size())
#define ll long long
#define ull unsigned long long
#define me(a, x) memset(a, x, sizeof(a))
using namespace std;
const int N = 1 << 20;
mt19937_64 orz;
int n, m;
vi e[N];
int ind[N], ord[N], top;
int dp[N], lst[N];
vector < pair < int, int > > ans;
int hm[N];
vi re[N];
vi qry(vi S) {
cout << "? ";
for(auto&u : S) {
cout << u << ' ';
}
cout << endl;
// vi ans;
// for(auto&p : S) {
// int cnt = 0;
// for(auto&v : re[p]) {
// cnt += hm[v];
// }
// ans.emplace_back(cnt);
// if(!cnt)
// hm[p] = 1;
// }
// for(auto&p : S)
// hm[p] = 0;
// cout << "ans = ";
// for(auto&u : ans) cout << u << ' ';
// cout << endl;
// return ans;
vi ret(sz(S));
L(i, 0, sz(ret) - 1) {
cin >> ret[i];
}
return ret;
}
vector < pair < int, int > > nans;
void slv(vi S, vi T, vi cnt) {
if(sz(S) == 1) {
L(i, 0, sz(T) - 1)
L(j, 1, cnt[i])
nans.emplace_back(S[0], T[i]),
cout << "add 1" << endl;
return ;
}
vi rT, rcnt;
L(i, 0, sz(T) - 1) {
if(cnt[i] == 0)
continue;
rT.emplace_back(T[i]);
rcnt.emplace_back(cnt[i]);
}
swap(T, rT), rT.clear();
swap(cnt, rcnt), rcnt.clear();
int mid = sz(S) / 2;
vi tmp;
L(i, 0, mid - 1)
tmp.emplace_back(S[i]);
L(i, 0, sz(T) - 1)
tmp.emplace_back(T[i]);
vi rm = qry(tmp);
L(z, mid, sz(rm) - 1) {
int ins = !rm[z];
int u = tmp[z];
for(auto &v : e[u]) rm[z] -= hm[v];
if(ins) hm[u] = true;
}
vi cntl(sz(T)), cntr(sz(T));
L(i, 0, sz(T) - 1) {
cntl[i] = rm[i + mid];
cntr[i] = cnt[i] - cntl[i];
}
vi Sl, Sr;
L(i, 0, sz(S) - 1) {
if(i < mid) {
Sl.emplace_back(S[i]);
} else {
Sr.emplace_back(S[i]);
}
}
slv(Sl, T, cntl);
slv(Sr, T, cntr);
}
void work(vi S) {
if(sz(S) <= 1) {
return ;
}
vi T = qry(S);
vi st, nt, cnt;
L(i, 0, sz(T) - 1) {
if(T[i] == 0) {
st.emplace_back(S[i]);
} else {
nt.emplace_back(S[i]);
cnt.emplace_back(T[i]);
}
}
work(nt);
nans.clear();
slv(st, nt, cnt);
for(auto &z : nans) {
int u = z.first;
int v = z.second;
ans.emplace_back(z);
e[u].emplace_back(v);
e[v].emplace_back(u);
}
}
void Add(int u, int v) {
re[u].emplace_back(v);
re[v].emplace_back(u);
}
int main() {
ios :: sync_with_stdio(false);
cin.tie(0); cout.tie(0);
Add(1, 2);
Add(1, 2);
Add(1, 3);
Add(4, 4);
Add(4, 5);
cin >> n;
vi S;
L(i, 1, n) S.emplace_back(i);
shuffle(S.begin(), S.end(), orz);
work(S);
L(i, 1, n) {
vi qwq = qry(vi{i, i});
if(qwq[1])
ans.emplace_back(make_pair(i, i));
}
cout << "! ";
cout << sz(ans) << ' ';
for(auto u : ans)
cout << u.first << ' ' << u.second << ' ';
cout << endl;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Time Limit Exceeded
input:
4 0 2 0
output:
? 3 2 1 4