Submission #779801

#	Time	Username	Problem	Language	Result	Execution time	Memory
779801		NK_	Carnival (CEOI14_carnival)	C++17	100 / 100	19 ms	208 KiB

carnival

// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>

using namespace std;

#define nl '\n'

template<class T> using V = vector<T>;
int main() {
	cin.tie(0)->sync_with_stdio(0);
	
	int N; cin >> N;
	V<int> P(N, -1);

	auto ask = [&](int x, int l, int r) {
		set<int> S;
		for(int i = l; i <= r; i++) S.insert(i);

		cout << size(S);
		for(auto v : S) cout << " " << v + 1;
		cout << endl;

		int res1; cin >> res1;

		S.insert(x);

		cout << size(S);
		for(auto v : S) cout << " " << v + 1;
		cout << endl;
	
		int res2; cin >> res2;

		return res1 == res2;
	};

	for(int i = 0; i < N; i++) {
		int lo = i, hi = N - 1;
		while(lo < hi) {
			int mid = (lo + hi + 1) / 2;
			// cout << lo << " " << mid << " " << hi << endl;
			if (ask(i, mid, hi)) lo = mid;
			else hi = mid - 1;
		}
		P[i] = lo;
	}	

	V<int> C(N, -1); int cur = 1;
	for(int i = N-1; i >= 0; i--) {
		// cout << i << " " << cur << endl;
		if (C[P[i]] == -1) {
			assert(P[i] == i);
			C[i] = cur++;
		} else C[i] = C[P[i]];
	}

	cout << 0;
	for(auto x : C) cout << " " << x;
	cout << endl;

    return 0;
}

• Subtask 1: 20 / 20
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 20 / 20
• Subtask 5: 20 / 20