QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#110987#4218. Hidden GraphRetrieve_72RE 16ms3784kbC++142.3kb2023-06-05 10:21:302023-06-05 10:21:31

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:21:31]
  • 评测
  • 测评结果:RE
  • 用时:16ms
  • 内存:3784kb
  • [2023-06-05 10:21:30]
  • 提交

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; ind[u] = 0;
		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]]);
			if (ind[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;
	}
	memcpy(ind, lnd, sizeof lnd);
}
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;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 3776kb

input:

3
1 2
1 3
2 3

output:

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

result:

ok correct

Test #2:

score: 0
Accepted
time: 2ms
memory: 3716kb

input:

10
1 2
1 3
-1 -1
-1 -1
1 4
4 5
2 5
-1 -1
-1 -1
2 6
-1 -1
-1 -1
-1 -1
3 7
-1 -1
-1 -1
-1 -1
-1 -1
3 8
4 8
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
3 9
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
3 10
4 10

output:

? 2 2 1 
? 2 3 1 
? 2 3 2 
? 3 4 2 3 
? 2 4 1 
? 3 5 2 4 
? 2 5 2 
? 2 5 3 
? 2 5 1 
? 4 6 2 3 4 
? 3 6 3 4 
? 2 6 1 
? 2 6 5 
? 4 7 2 3 4 
? 3 7 2 4 
? 2 7 6 
? 2 7 1 
? 2 7 5 
? 4 8 3 4 6 
? 3 8 4 6 
? 2 8 6 
? 3 8 2 7 
? 2 8 1 
? 2 8 5 
? 5 9 1 5 6 8 
? 2 9 7 
? 2 9 2 
? 2 9 3 
? 2 9 4 
? 5 10 1 ...

result:

ok correct

Test #3:

score: 0
Accepted
time: 3ms
memory: 3776kb

input:

5
2 1
3 1
3 2
4 1
4 2
-1 -1
-1 -1
5 1
5 2

output:

? 2 2 1 
? 2 3 1 
? 2 3 2 
? 2 4 1 
? 2 4 2 
? 2 4 3 
? 3 5 3 4 
? 2 5 1 
? 2 5 2 
! 7
1 2
1 3
1 4
1 5
2 3
2 4
2 5

result:

ok correct

Test #4:

score: 0
Accepted
time: 2ms
memory: 3784kb

input:

3
2 1
1 3
-1 -1

output:

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

result:

ok correct

Test #5:

score: 0
Accepted
time: 2ms
memory: 3776kb

input:

6
1 2
3 1
3 2
-1 -1
4 2
3 4
4 5
-1 -1
2 5
3 5
-1 -1
-1 -1
3 6
-1 -1

output:

? 2 2 1 
? 2 3 1 
? 2 3 2 
? 2 4 1 
? 2 4 2 
? 2 4 3 
? 3 5 1 4 
? 2 5 1 
? 2 5 2 
? 2 5 3 
? 3 6 1 4 
? 2 6 2 
? 2 6 3 
? 2 6 5 
! 9
1 2
1 3
2 3
2 4
2 5
3 4
3 5
3 6
4 5

result:

ok correct

Test #6:

score: 0
Accepted
time: 7ms
memory: 3708kb

input:

27
-1 -1
3 1
3 2
-1 -1
-1 -1
-1 -1
3 5
-1 -1
1 5
2 5
-1 -1
6 1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
1 8
-1 -1
-1 -1
6 8
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
1 9
-1 -1
10 8
-1 -1
-1 -1
-1 -1
-1 -1
4 11
6 11
-1 -1
5 11
-1 -1
-1 -1
-1 -1
-1 -1
1 11
12 11
-1 -1
5 12
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
8 13
-1 -1
-1 -...

output:

? 2 2 1 
? 2 3 1 
? 2 3 2 
? 2 4 1 
? 2 4 2 
? 2 4 3 
? 3 5 3 4 
? 2 5 4 
? 2 5 1 
? 2 5 2 
? 3 6 3 4 
? 2 6 1 
? 2 6 2 
? 2 6 5 
? 3 7 1 4 
? 3 7 3 6 
? 2 7 2 
? 2 7 5 
? 3 8 1 4 
? 2 8 4 
? 3 8 3 7 
? 3 8 5 6 
? 2 8 5 
? 2 8 2 
? 4 9 3 4 6 
? 4 9 5 7 8 
? 2 9 2 
? 2 9 1 
? 4 10 3 4 6 
? 4 10 5 7 8...

result:

ok correct

Test #7:

score: 0
Accepted
time: 9ms
memory: 3756kb

input:

47
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
5 3
5 4
-1 -1
-1 -1
-1 -1
-1 -1
7 5
-1 -1
-1 -1
7 6
-1 -1
-1 -1
5 8
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
9 4
-1 -1
10 7
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
11 1
7 11
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
7 12
2 12
-1 -1
5 12
-1 -1
12 ...

output:

? 2 2 1 
? 2 3 1 
? 2 3 2 
? 2 4 1 
? 2 4 2 
? 2 4 3 
? 2 5 1 
? 2 5 2 
? 2 5 3 
? 2 5 4 
? 3 6 1 5 
? 2 6 2 
? 2 6 3 
? 2 6 4 
? 3 7 1 5 
? 2 7 1 
? 2 7 2 
? 2 7 6 
? 2 7 3 
? 2 7 4 
? 3 8 1 5 
? 2 8 1 
? 3 8 2 7 
? 2 8 3 
? 2 8 4 
? 2 8 6 
? 4 9 1 7 8 
? 3 9 2 5 
? 2 9 3 
? 2 9 4 
? 2 9 6 
? 4 10 ...

result:

ok correct

Test #8:

score: 0
Accepted
time: 16ms
memory: 3676kb

input:

38
-1 -1
-1 -1
-1 -1
4 1
-1 -1
-1 -1
4 5
-1 -1
3 5
1 5
4 6
-1 -1
-1 -1
-1 -1
-1 -1
4 7
2 7
-1 -1
7 5
6 7
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
4 10
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
11 4
-1 -1
-1 -1
-1 -1
-1 -1
11 1
-1 -1
12 8
12 7
-1 -1
11 12
-1 -1
-1 -1
-1 -1
-1 -1
-1...

output:

? 2 2 1 
? 2 3 1 
? 2 3 2 
? 2 4 1 
? 2 4 2 
? 2 4 3 
? 3 5 2 4 
? 2 5 2 
? 2 5 3 
? 2 5 1 
? 3 6 2 4 
? 2 6 2 
? 2 6 3 
? 2 6 1 
? 2 6 5 
? 3 7 2 4 
? 2 7 2 
? 2 7 3 
? 3 7 5 6 
? 2 7 6 
? 2 7 1 
? 4 8 2 5 6 
? 3 8 3 4 
? 2 8 1 
? 2 8 7 
? 4 9 5 6 8 
? 3 9 2 4 
? 2 9 3 
? 2 9 1 
? 2 9 7 
? 4 10 5 6...

result:

ok correct

Test #9:

score: 0
Accepted
time: 1ms
memory: 3648kb

input:

25
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
5 2
-1 -1
5 4
-1 -1
-1 -1
-1 -1
6 4
5 7
-1 -1
7 3
-1 -1
-1 -1
4 8
-1 -1
2 8
-1 -1
-1 -1
5 8
9 4
-1 -1
-1 -1
9 8
-1 -1
2 9
-1 -1
10 3
-1 -1
-1 -1
-1 -1
9 11
-1 -1
-1 -1
10 11
-1 -1
2 11
-1 -1
12 4
-1 -1
6 12
-1 -1
-1 -1
-1 -1
-1 -1
7 13
-1 -1
-1 -1
13 8
6 ...

output:

? 2 2 1 
? 2 3 1 
? 2 3 2 
? 2 4 1 
? 2 4 2 
? 2 4 3 
? 2 5 1 
? 2 5 2 
? 2 5 3 
? 2 5 4 
? 3 6 1 5 
? 2 6 3 
? 2 6 2 
? 2 6 4 
? 4 7 1 5 6 
? 3 7 1 6 
? 2 7 3 
? 2 7 2 
? 2 7 4 
? 4 8 1 4 7 
? 3 8 1 7 
? 2 8 2 
? 2 8 3 
? 2 8 6 
? 2 8 5 
? 4 9 1 4 7 
? 3 9 1 7 
? 3 9 3 5 
? 3 9 6 8 
? 2 9 6 
? 2 9 ...

result:

ok correct

Test #10:

score: 0
Accepted
time: 3ms
memory: 3704kb

input:

6
-1 -1
-1 -1
2 3
-1 -1
-1 -1
-1 -1
-1 -1
2 5
-1 -1
-1 -1
-1 -1
5 6

output:

? 2 2 1 
? 2 3 1 
? 2 3 2 
? 3 4 1 3 
? 2 4 2 
? 3 5 1 3 
? 2 5 4 
? 2 5 2 
? 3 6 1 2 
? 2 6 4 
? 2 6 3 
? 2 6 5 
! 3
2 3
2 5
5 6

result:

ok correct

Test #11:

score: 0
Accepted
time: 2ms
memory: 3700kb

input:

3
2 1
3 1
2 3

output:

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

result:

ok correct

Test #12:

score: 0
Accepted
time: 2ms
memory: 3712kb

input:

3
2 1
3 1
-1 -1

output:

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

result:

ok correct

Test #13:

score: 0
Accepted
time: 3ms
memory: 3640kb

input:

5
2 1
3 1
2 3
-1 -1
-1 -1
-1 -1
2 5
-1 -1
5 1
-1 -1

output:

? 2 2 1 
? 2 3 1 
? 2 3 2 
? 2 4 1 
? 2 4 2 
? 2 4 3 
? 3 5 2 4 
? 2 5 4 
? 2 5 1 
? 2 5 3 
! 5
1 2
1 3
1 5
2 3
2 5

result:

ok correct

Test #14:

score: 0
Accepted
time: 3ms
memory: 3708kb

input:

3
2 1
-1 -1
-1 -1

output:

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

result:

ok correct

Test #15:

score: 0
Accepted
time: 0ms
memory: 3672kb

input:

5
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
4 3
-1 -1
2 5
3 5

output:

? 2 2 1 
? 2 3 1 
? 2 3 2 
? 2 4 1 
? 2 4 2 
? 2 4 3 
? 3 5 1 4 
? 2 5 2 
? 2 5 3 
! 3
2 5
3 4
3 5

result:

ok correct

Test #16:

score: -100
Runtime Error

input:

93
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
10 9
-1 -1
-1 -1
-1 -1
-1 -1
-1 -...

output:

? 2 2 1 
? 2 3 1 
? 2 3 2 
? 2 4 1 
? 2 4 2 
? 2 4 3 
? 2 5 1 
? 2 5 2 
? 2 5 3 
? 2 5 4 
? 2 6 1 
? 2 6 2 
? 2 6 3 
? 2 6 4 
? 2 6 5 
? 2 7 1 
? 2 7 2 
? 2 7 3 
? 2 7 4 
? 2 7 5 
? 2 7 6 
? 2 8 1 
? 2 8 2 
? 2 8 3 
? 2 8 4 
? 2 8 5 
? 2 8 6 
? 2 8 7 
? 2 9 1 
? 2 9 2 
? 2 9 3 
? 2 9 4 
? 2 9 5 
? 2...

result: