QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#198857 | #7510. Independent Set | GenshinImpactsFault# | WA | 1ms | 3536kb | C++20 | 2.2kb | 2023-10-03 17:56:01 | 2023-10-03 17:56:01 |
Judging History
answer
#include<bits/stdc++.h>
#define inf 1e9
#define eps 1e-6
#define FOR(i, a, b) for(int i = a; i <= b; i ++)
#define REP(i, a, b) for(int i = a; i >= b; i --)
#define pb push_back
#define fr first
#define sd second
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
inline ll read()
{
char ch = getchar();
ll s = 0, w = 1;
while (ch < '0' || ch > '9') {if (ch == '-')w = -1; ch = getchar();}
while (ch >= '0' && ch <= '9') {s = s * 10 + ch - '0'; ch = getchar();}
return s * w;
}
#define N 4010
int n, m;
int S = 0, cnt[N];
vector<pair<int, int>>ans;
void ask(int l, int r, const vector<int>a)
{
for (int x : a)cnt[x] = 0;
int k = r - l + 1 + a.size(); S += k; assert(S <= 176000);
cout << "? "; cout << k << ' ';
FOR(i, l, r)cout << i << ' ';
for (int x : a)if (x >= l && x <= r)cout << x << ' ';
for (int x : a)if (x < l || x > r)cout << x << ' ';
cout << endl;
FOR(i, l, r) {int x; cin >> x;}
for (int x : a)if (x >= l && x <= r)
{
int t;
cin >> t; cnt[x] = t;
}
for (int x : a)if (x < l || x > r)
{
int t;
cin >> t; cnt[x] = t;
}
vector<int>b;
for (int x : a)if (x < l || x > r)b.push_back(x);
k = b.size(); S += k; assert(S <= 176000);
if (k == 0)return ;
cout << "? "; cout << k << ' ';
for (int x : b)cout << x << ' '; cout << endl;
for (int x : b)
{
int t;
cin >> t; cnt[x] -= t;
}
}
void sol(int l, int r, vector<int>c)
{
// cerr << "GG:" << l << ' ' << r << endl;
while (!c.empty() && c.back() > r)c.pop_back();
// for (int x : c)cout << x << ' '; cout << endl;
if (c.empty())return ;
ask(l, r, c);
if (l == r)
{
for (int x : c)while (cnt[x] --)ans.push_back({x, l});
return ;
}
vector<int>A; int mid = (l + r) >> 1;
for (int x : c)if (cnt[x])A.push_back(x);
// cerr << "ED:" << l << ' ' << r << endl;
// for (int x : A)cout << x << ' '; cout << endl;
sol(l, mid, A); sol(mid + 1, r, A);
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n;
vector<int>a(n);
FOR(i, 0, n - 1)a[i] = i + 1;
sol(1, n, a);
cout << "!" << ' ';
cout << ans.size() << ' ';
for (auto [x, y] : ans)cout << x << ' ' << y << ' '; cout << endl;
return 0;
}
/*
6
4 6 8 9 2 4
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 3536kb
input:
4 0 2 1 0 0 2 1 1 0 2 2 0 0 0 0 0 1 0 0 0 1
output:
? 8 1 2 3 4 1 2 3 4 ? 3 1 2 2 ? 2 2 2 ? 5 3 4 3 4 2 ? 1 2 ? 2 4 4 ! 1 4 4
result:
wrong answer Wrong graph