QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#198857#7510. Independent SetGenshinImpactsFault#WA 1ms3536kbC++202.2kb2023-10-03 17:56:012023-10-03 17:56:01

Judging History

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

  • [2023-10-03 17:56:01]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3536kb
  • [2023-10-03 17:56:01]
  • 提交

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