oj.uz

답안 #37034

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
37034 2017-12-20T15:00:52 Z aome 사육제 (CEOI14_carnival) C++14
100 / 100
 19 ms 2016 KB 
#include <bits/stdc++.h>
using namespace std;

const int N = 155;

int par[N], color[N];

int find(int u) {
	return (u == par[u]) ? u : par[u] = find(par[u]);
}

void join(int u, int v) {
	par[find(u)] = find(v);
}

int get(vector<int> &go, int l, int r) {
	cout << r - l + 1 << ' ';
	for (int i = l; i <= r; ++i) cout << go[i] << ' '; cout << '\n';
	int res; cin >> res; return res;
}

void solve(vector<int> &go) {
	int sz = go.size();
	int l = 0, r = sz - 1;
	while (l < r) {
		int mid = (l + r) >> 1;
		if (get(go, 0, mid) == mid + 1) l = mid + 1;
		else r = mid;
	}
	if (get(go, 0, l) == l + 1) return;
	int pos = l;
	l = 0, r = pos - 1;
	while (l < r) {
		int mid = (l + r + 1) >> 1;
		if (get(go, mid, pos) == pos - mid + 1) r = mid - 1;
		else l = mid;
	}
	join(go[pos], go[l]);
	vector<int> tmp = go; go.clear();
	for (int i = 0; i < sz; ++i) {
		if (i != pos) go.push_back(tmp[i]);
	}
	solve(go);
}

int main() {
	int n; cin >> n;
	vector<int> go;
	for (int i = 1; i <= n; ++i) par[i] = i, go.push_back(i);
	solve(go);
	int cnt = 0;
	for (int i = 1; i <= n; ++i) {
		if (find(i) == i) color[i] = ++cnt;
	}
	cout << "0 ";
	for (int i = 1; i <= n; ++i) {
		cout << color[find(i)] << ' ';
	}
}

Subtask #1
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 2016 KB Output is correct
2 Correct 16 ms 2016 KB Output is correct
3 Correct 0 ms 2016 KB Output is correct
4 Correct 0 ms 2016 KB Output is correct
5 Correct 3 ms 2016 KB Output is correct
6 Correct 3 ms 2016 KB Output is correct
7 Correct 16 ms 2016 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 2016 KB Output is correct
2 Correct 13 ms 2016 KB Output is correct
3 Correct 9 ms 2016 KB Output is correct
4 Correct 3 ms 2016 KB Output is correct
5 Correct 3 ms 2016 KB Output is correct
6 Correct 9 ms 2016 KB Output is correct
7 Correct 16 ms 2016 KB Output is correct

Subtask #3
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 2016 KB Output is correct
2 Correct 6 ms 2016 KB Output is correct
3 Correct 9 ms 2016 KB Output is correct
4 Correct 0 ms 2016 KB Output is correct
5 Correct 0 ms 2016 KB Output is correct
6 Correct 9 ms 2016 KB Output is correct
7 Correct 13 ms 2016 KB Output is correct

Subtask #4
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 2016 KB Output is correct
2 Correct 6 ms 2016 KB Output is correct
3 Correct 3 ms 2016 KB Output is correct
4 Correct 0 ms 2016 KB Output is correct
5 Correct 3 ms 2016 KB Output is correct
6 Correct 6 ms 2016 KB Output is correct
7 Correct 13 ms 2016 KB Output is correct

Subtask #5
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 2016 KB Output is correct
2 Correct 0 ms 2016 KB Output is correct
3 Correct 9 ms 2016 KB Output is correct
4 Correct 6 ms 2016 KB Output is correct
5 Correct 9 ms 2016 KB Output is correct
6 Correct 9 ms 2016 KB Output is correct
7 Correct 3 ms 2016 KB Output is correct