QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#110986#4218. Hidden GraphRetrieve_72TL 0ms0kbC++142.2kb2023-06-05 10:17:512023-06-05 10:17:55

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-06-05 10:17:55]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:0kb
  • [2023-06-05 10:17:51]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define pii pair<int, int>
#define mp make_pair
#define fi first
#define se second 
#define deb(var) cerr << #var << '=' << var << "; "
#define int long long
int n, m, tot, ind[2010], lnd[2010], col[2010];
set<int> sub[2010], tmp; vector<int> g[2010];
void getsub(int n) {
	set<pii> st; st.clear();
	for (int i = 1; i <= n; i++)
		st.insert(mp(ind[i], i));
	memcpy(lnd, ind, sizeof lnd);
	memset(col, 0, sizeof col); tot = 0;
	while (st.size()) {
		set<pii>::iterator it = st.begin(); st.erase(it);
		int u = (*it).se;
		vector<int> c; c.clear();
		for (int j = 0; j < g[u].size(); j++) {
			if (col[g[u][j]]) c.pb(col[g[u][j]]);
			st.erase(mp(ind[g[u][j]], g[u][j])); ind[g[u][j]]--; st.insert(mp(ind[g[u][j]], g[u][j]));
		}
		sort(c.begin(), c.end());
		int lst = 0, now = 0;
		for (int i = 0; i < c.size(); i++)
			if (c[i] > lst + 1) {
				now = lst + 1; break;
			} else lst = c[i];
		col[u] = now;
		if (!now) col[u] = now = ++tot;
	}
}
signed main() {
	srand(time(0));
	cin >> n;
	tot = 1; sub[1].insert(1);
	for (int i = 2; i <= n; i++) {
		for (int j = 1; j <= tot; j++) {
			cout << "? " << sub[j].size() + 1 << " " << i << " ";
			tmp = sub[j];
			for (set<int>::iterator it = tmp.begin(); it != tmp.end(); it++) cout << *it << " "; cout << endl;
			int u, v;
			cin >> u >> v;
			if (u != i) swap(u, v);
			if (u == -1 && v == -1) {
			}
			else {
				g[u].pb(v), g[v].pb(u); m++; ind[u]++, ind[v]++;
				while (true) {
					tmp.erase(v);
					if (tmp.empty()) break;
					cout << "? " << tmp.size() + 1 << " " << i << " ";
					for (set<int>::iterator it = tmp.begin(); it != tmp.end(); it++) cout << *it << " "; cout << endl;
					cin >> u >> v;
					if (u != i) swap(u, v); 
					if (v != -1) {
						g[u].pb(v), g[v].pb(u); m++; ind[u]++, ind[v]++;
					} else break;
				}
			}
		}
		for (int i = 1; i <= tot; i++) sub[i].clear();
		getsub(i);
		for (int j = 1; j <= i; j++) sub[col[j]].insert(j);
	}
	cout << "! " << m << endl;
	for (int i = 1; i <= n; i++) {
		for (int j = 0; j < g[i].size(); j++)
			if (g[i][j] > i) cout << i << " " << g[i][j] << endl;
	}
	return 0;
}

詳細信息

Test #1:

score: 0
Time Limit Exceeded

input:

3
1 2

output:

? 2 2 1 

result: