Submission #534609

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
534609	2022-03-08T11:47:22 Z	shrimb	Carnival (CEOI14_carnival)	C++17	20 / 100	102 ms	296 KB

carnival

#include"bits/stdc++.h"
#define int long long
// #define endl '\n'
using namespace std;

int dsu[2000001];
int ans[2000001];

int Find (int x) {
	return dsu[x] == x ? x : dsu[x] = Find(dsu[x]);
}

void Union (int a, int b) {
	dsu[Find(a)] = Find(b);
}

bool Query (int a, int b) {
	cout << "2 " << a << " " << b << endl;
	int x;
	cin >> x;
	return x == 1;
}


signed main () {

	int n;
	cin >> n;
	set<pair<int,int>> s;
	vector<int> num;
	for (int i = 1 ; i <= n ; i++) s.insert({1, i}), dsu[i] = i;
	while (s.size() > 1) {
		auto [X, Y] = *s.begin();
		s.erase(s.begin());
		bool found = 0;
		for (auto [A, B] : s) {
			if (Query(Y, B)) {
				found = 1;
				Union(B, Y);
				s.erase({A, B});
				s.insert({A + X, Find(B)});
				break;
			}
		}
		if (!found) {
			num.push_back(Y);
		}
	}
	auto [X, Y] = *s.begin();
	num.push_back(Y);
	int c = 1;
	for (int i = 1 ; i <= n ; i++) if (dsu[i] == i) ans[i] = c++;
	cout << 0 << " ";
	for (int i = 1 ; i <= n ; i++) cout << ans[Find(i)] << " ";
}

Subtask #1

4.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	200 KB	Output is correct
2	Correct	36 ms	200 KB	Output is correct
3	Partially correct	55 ms	200 KB	Partially correct
4	Partially correct	94 ms	200 KB	Partially correct
5	Correct	4 ms	200 KB	Output is correct
6	Correct	3 ms	200 KB	Output is correct
7	Correct	36 ms	200 KB	Output is correct

Subtask #2

4.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6 ms	200 KB	Output is correct
2	Correct	24 ms	200 KB	Output is correct
3	Partially correct	35 ms	200 KB	Partially correct
4	Partially correct	73 ms	200 KB	Partially correct
5	Correct	11 ms	200 KB	Output is correct
6	Correct	16 ms	200 KB	Output is correct
7	Correct	15 ms	200 KB	Output is correct

Subtask #3

4.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	288 KB	Output is correct
2	Correct	7 ms	200 KB	Output is correct
3	Partially correct	35 ms	200 KB	Partially correct
4	Partially correct	84 ms	200 KB	Partially correct
5	Correct	29 ms	200 KB	Output is correct
6	Partially correct	31 ms	296 KB	Partially correct
7	Partially correct	42 ms	200 KB	Partially correct

Subtask #4

4.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	200 KB	Output is correct
2	Correct	3 ms	200 KB	Output is correct
3	Partially correct	89 ms	200 KB	Partially correct
4	Partially correct	102 ms	296 KB	Partially correct
5	Partially correct	47 ms	200 KB	Partially correct
6	Partially correct	66 ms	296 KB	Partially correct
7	Partially correct	35 ms	292 KB	Partially correct

Subtask #5

4.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	200 KB	Output is correct
2	Correct	16 ms	200 KB	Output is correct
3	Partially correct	68 ms	296 KB	Partially correct
4	Partially correct	60 ms	292 KB	Partially correct
5	Partially correct	61 ms	200 KB	Partially correct
6	Partially correct	88 ms	296 KB	Partially correct
7	Partially correct	58 ms	200 KB	Partially correct