QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#405180#4218. Hidden GraphieeWA 1ms3836kbC++141.9kb2024-05-05 13:14:392024-05-05 13:14:41

Judging History

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

  • [2024-05-05 13:14:41]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3836kb
  • [2024-05-05 13:14:39]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for (int i = (a); i <= (b); i++)
pair<int, int> query(vector<int> v) {
	cout << "?" << " " << v.size();
	for (int x : v) {
		cout << " " << x;
	}
	cout << endl;
	int x, y;
	cin >> x >> y;
	return {x, y};
}
constexpr int N = 2005;
int n, p;
vector<int> e[N];
int deg[N];
int k;
int col[N];
vector<int> vec[N];
void coloring() {
	set<pair<int, int>> se;
	rep(u, 1, p - 1) {
		se.insert({deg[u] = e[u].size(), u});
	}
	vector<int> del(p);
	vector<int> seq;
	while (se.size()) {
		auto [d, u] = *se.begin();
		se.erase(se.begin());
		seq.push_back(u);
		del[u] = 1;
		for (int v : e[u]) {
			if (!del[v]) {
				se.erase({deg[v], v});
				deg[v]--;
				se.insert({deg[v], v});
			}
		}
	}
	reverse(seq.begin(), seq.end());
	static bool dic[N], in[N];
	rep(u, 1, p - 1) {
		dic[u] = 0;
		in[u] = 0;
	}
	for (int u : seq) {
		for (int v : e[u]) {
			if (dic[v]) {
				in[col[v]] = 1;
			}
		}
		int mex = 1;
		while (in[mex]) {
			mex++;
		}
		if (mex > k) k++;
		col[u] = mex;
		for (int v : e[u]) {
			if (dic[v]) {
				in[col[v]] = 0;
			}
		}
		dic[u] = 1;
	}
	rep(i, 1, N - 1) {
		vec[i].clear();
	}
	rep(u, 1, p - 1) {
		vec[col[u]].push_back(u);
	}
}
void solve(vector<int> nodes) {
	nodes.push_back(p);
	while (nodes.size() >= 2) {
		auto [x, y] = query(nodes);
		if (x == -1 && y == -1) return;
		assert(x == p || y == p);
		e[x].push_back(y);
		e[y].push_back(x);
		nodes.erase(find(nodes.begin(), nodes.end(), x ^ y ^ p));
	}
}
int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin >> n;
	for (p = 2; p <= n; p++) {
		coloring();
		rep(id, 1, k) solve(vec[id]);
	}
	vector<array<int, 2>> edges;
	rep(u, 1, n) rep(v, 1, u - 1) if (e[u][v]) edges.push_back({u, v});
	cout << "!" << " " << edges.size() << "\n";
	for (auto [u, v] : edges) {
		cout << u << " " << v << "\n";
	}
	cout << flush;
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 1ms
memory: 3836kb

input:

3
1 2
2 3
1 3

output:

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

result:

wrong answer read 2 edges but expected 3 edges