oj.uz

답안 #37033

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
37033 2017-12-20T15:00:06 Z aome 사육제 (CEOI14_carnival) C++14
0 / 100
 9 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 << '\n';
	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;
	}
	for (int i = 1; i <= n; ++i) {
		cout << color[find(i)] << ' ';
	}
}

Subtask #1
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 9 ms 2016 KB Same person came twice to the party.
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 9 ms 2016 KB Same person came twice to the party.
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 2016 KB Unexpected end of file - int32 expected
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 6 ms 2016 KB Same person came twice to the party.
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 6 ms 2016 KB Same person came twice to the party.
2 Halted 0 ms 0 KB -