oj.uz

답안 #534642

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
534642 2022-03-08T12:29:47 Z shrimb 사육제 (CEOI14_carnival) C++17
20 / 100
 125 ms 300 KB 
#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.end();
		s.erase(--s.end());
		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

# 결과 실행 시간 메모리 Grader output
1 Partially correct 56 ms 200 KB Partially correct
2 Partially correct 29 ms 200 KB Partially correct
3 Partially correct 33 ms 200 KB Partially correct
4 Partially correct 67 ms 200 KB Partially correct
5 Correct 35 ms 200 KB Output is correct
6 Correct 4 ms 200 KB Output is correct
7 Partially correct 28 ms 200 KB Partially correct

Subtask #2
4.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Partially correct 48 ms 200 KB Partially correct
2 Partially correct 49 ms 200 KB Partially correct
3 Partially correct 54 ms 200 KB Partially correct
4 Partially correct 102 ms 200 KB Partially correct
5 Correct 37 ms 200 KB Output is correct
6 Correct 11 ms 200 KB Output is correct
7 Partially correct 45 ms 200 KB Partially correct

Subtask #3
4.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 200 KB Output is correct
2 Partially correct 41 ms 200 KB Partially correct
3 Partially correct 78 ms 200 KB Partially correct
4 Partially correct 111 ms 200 KB Partially correct
5 Correct 29 ms 200 KB Output is correct
6 Correct 29 ms 200 KB Output is correct
7 Partially correct 61 ms 296 KB Partially correct

Subtask #4
4.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Partially correct 35 ms 200 KB Partially correct
2 Partially correct 44 ms 200 KB Partially correct
3 Partially correct 90 ms 300 KB Partially correct
4 Partially correct 125 ms 200 KB Partially correct
5 Partially correct 40 ms 200 KB Partially correct
6 Partially correct 54 ms 200 KB Partially correct
7 Partially correct 62 ms 300 KB Partially correct

Subtask #5
4.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 31 ms 200 KB Output is correct
2 Partially correct 61 ms 200 KB Partially correct
3 Partially correct 69 ms 292 KB Partially correct
4 Partially correct 100 ms 292 KB Partially correct
5 Partially correct 71 ms 200 KB Partially correct
6 Partially correct 67 ms 200 KB Partially correct
7 Partially correct 81 ms 296 KB Partially correct