Submission #992699

#	Time	Username	Problem	Language	Result	Execution time	Memory
992699		aaargh	Carnival (CEOI14_carnival)	C++17	100 / 100	9 ms	688 KiB

carnival

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define nl '\n'
// #define io ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define pii pair<int,int>

int query(int n, vector<int> people) {
	cout << n;
	for (int i = 0; i < n; i++) {
		cout << " " << people[i]; 
	}
	cout << endl;
	int temp;
	cin >> temp;
	return temp;
} 

void output(vector<int> v) {
	cout << 0;
	for (int e: v) cout << " " << e;
	cout << endl;
}

signed main() {
	// io;
	int n; cin >> n;
	vector<int> unique;
	unique.push_back(1);
	vector<int> costumes; 
	costumes.push_back(1);
	int prev, temp, temp2, temp3;
	//vector<int> nums;
	//nums.push_back(1);
	int maxcost = 1; 
	prev = 1;
	for (int i = 1; i < n; i++) {
		// first one is always unique
		unique.push_back(i+1);
		temp = query(unique.size(), unique);
		if (temp == prev+1) {
			// unique.push_back()
			// keep it in unique and add to costumes
			costumes.push_back(maxcost+1);
			maxcost++;
		} else {
			unique.pop_back();
			// check which one it is the same as
			int l = 0, r = unique.size()-1;
			int mid;

			while (r - l >= 1) {
				// cerr << "hi" << nl;
				mid = (l+r)/2;
				// query lower range if in or not
				vector<int> v(unique.begin()+l, unique.begin()+mid+1);
				temp2 = query(mid-l+1, v); // 0 to mid-1
				v.push_back(i+1);
				temp3 = query(mid-l+2, v);
				if (temp2  == temp3) {
					r = mid; // it could be in l to mid inclusive
				} else {
					l = mid+1; // it could be in mid+1 to r
				}
			}
			mid = (l+r)/2;
			// cout << "mid is " << unique[mid];
			costumes.push_back(costumes[unique[mid]-1]);

		}
		prev = temp;
	}
	output(costumes);
}

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