Submission #37034

#	Time	Username	Problem	Language	Result	Execution time	Memory
37034		aome	Carnival (CEOI14_carnival)	C++14	100 / 100	19 ms	2016 KiB

carnival

#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 / 20
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 20 / 20
• Subtask 5: 20 / 20