Submission #70394

#	Time	Username	Problem	Language	Result	Execution time	Memory
70394		spencercompton	Carnival (CEOI14_carnival)	C++17	100 / 100	25 ms	700 KiB

carnival

#include <bits/stdc++.h>
using namespace std;

bool query(vector<int> li){
	cout << li.size();
	for(int i = 0; i<li.size(); i++){
		cout << " " << (li[i]+1);
	}
	cout << endl;
	int x;
	cin >> x;
	return x<li.size();
}
vector<int> sub(vector<int> a, int l, int r){
	vector<int> ret;
	for(int i = l; i<=r; i++){
		ret.push_back(a[i]);
	}
	return ret;
}
vector<int> comp[150];
int id[150];
int sz[150];
int main(){
	int n;
	cin >> n;
	vector<int> all;
	for(int i = 0; i<n; i++){
		all.push_back(i);
		id[i] = i;
		sz[i] = 1;
		comp[i].push_back(i);
	}
	while(query(all)){
		int lo = 0;
		int hi = all.size()-1;
		while(lo<hi){
			int mid = (lo+hi)/2;
			if(query(sub(all,0,mid))){
				hi = mid;
			}
			else{
				lo = mid+1;
			}
		}
		int en = lo;
		lo = 0;
		hi = en;
		while(lo<hi){
			int mid = (lo+hi+1)/2;
			if(query(sub(all,mid,en))){
				lo = mid;
			}
			else{
				hi = mid-1;
			}
		}
		int a = all[lo];
		int b = all[en];
		int ca = id[a];
		int cb = id[b];
		for(int i = 0; i<comp[ca].size(); i++){
			comp[cb].push_back(comp[ca][i]);
			id[comp[ca][i]] = cb;
			sz[cb]++;
		}
		comp[ca].clear();
		vector<int> nex;
		for(int i = 0; i<all.size(); i++){
			if(i==en){
				continue;
			}
			nex.push_back(all[i]);
		}
		all = nex;
	}
	map<int, int> ma;
	int point = 1;
	for(int i = 0; i<n; i++){
		if(ma.find(id[i])==ma.end()){
			ma[id[i]] = point++;
		}
	}
	cout << 0;
	for(int i = 0; i<n; i++){
		cout << " " << ma[id[i]];
	}
	cout << endl;
}

Compilation message (stderr)

carnival.cpp: In function 'bool query(std::vector<int>)':
carnival.cpp:7:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i<li.size(); i++){
                 ~^~~~~~~~~~
carnival.cpp:13:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  return x<li.size();
         ~^~~~~~~~~~
carnival.cpp: In function 'int main()':
carnival.cpp:63:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i<comp[ca].size(); i++){
                  ~^~~~~~~~~~~~~~~~
carnival.cpp:70:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i<all.size(); i++){
                  ~^~~~~~~~~~~

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