Submission #551344

#	Time	Username	Problem	Language	Result	Execution time	Memory
551344		AugustinasJucas	Carnival (CEOI14_carnival)	C++14	100 / 100	16 ms	312 KiB

carnival

#include <bits/stdc++.h>
using namespace std;
const int dydis = 151;
int type[dydis];
int n;
int ask(vector<int> vec) {
	cout << vec.size() << " ";
	for(auto &x : vec) cout << x+1 << " ";
	cout << endl; 
	int ans;
	cin >> ans;
	return ans;
}
int tevas[dydis];
int fp(int v) {
	if(tevas[v] == v) return v;
	return tevas[v] = fp(tevas[v]);
}
void merge(int a, int b) {
	a = fp(a);
	b = fp(b);
	tevas[a] = b;
}
vector<int> prm(int i1, vector<int> a) {
	vector<int> ret;
	for(int i = 0; i <= i1; i++) ret.push_back(a[i]);
	return ret;
}
void compTevas(){
	vector<int> visi;
	for(int i = 0; i < n; i++) {
		if(fp(i) == i) visi.push_back(i);
	}
	sort(visi.begin(), visi.end());
	for(int i = 0; i < n; i++) {
		type[i] = lower_bound(visi.begin(), visi.end(), fp(i)) - visi.begin();
	}
} 
int main () {
	for(int i = 0; i < dydis; i++) tevas[i] = i;
	cin >> n;
	for(int i = 0; i < n; i++) type[i] = -1;
	
	vector<int> list;
	for(int i = 0; i < n; i++) {
		list.push_back(i);
	}
	
	while(list.size()) {
		int i1 = list.size();
		int l = 0; int r = list.size()-1; int mid;
		while(l <= r) {
			mid = (l + r) / 2;
			if(ask(prm(mid, list)) != mid+1) {	
				r = mid-1;
				i1 = mid;
			}else {
				l = mid+1;
			}
		}
		if(i1 == (int)list.size()) break;
		l = 0; r = i1; 
		int i2 = -1;
		while(l <= r) {
			mid = (l + r) / 2;
			vector<int> visi;
			for(int j = mid; j <= i1; j++) visi.push_back(list[j]);
			if(ask(visi) == i1 - mid + 1) {
				r = mid-1;
			}else {
				l = mid+1;
				i2 = mid;
			}
		}
		merge(list[i1], list[i2]);
		list.erase(list.begin()+i1);
	}
	
	compTevas();
	
	cout << "0 ";
	for(int i = 0; i < n; i++) {
		cout << type[i] + 1 << " ";
	}
	cout << endl;
	
	
	return 0;
}

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