Submission #304738

#	Time	Username	Problem	Language	Result	Execution time	Memory
304738		sofapuden	Carnival (CEOI14_carnival)	C++14	100 / 100	14 ms	384 KiB

carnival

#include <bits/stdc++.h>

using namespace std;

vector<int> used;
vector<int> unused;
vector<int> output;
int k = 0;

int find2(int lo, int hi, int target){
	int x;
	cout << hi-lo+2 << " ";
	for(int i = lo; i <= hi; ++i){
		cout << used[i] << " ";
	}
	cout << target << endl;
	cin >> x;
	if(x == hi-lo+2)return -1;
	if(hi == lo){
		output[target-1] = output[used[hi]-1];
		return hi;
	}
	int y = find2(lo, (lo+hi)/2, target);
	if(y != -1)return y;
	else return find2((lo+hi)/2+1, hi, target);
}
		

void find(int lo, int hi){
	k++;
	cout << hi-lo+1+(int)used.size() << " ";
	for(int i = 0; i < (int)used.size(); ++i){
		cout << used[i] << " ";
	}
	for(int i = lo; i <= hi; ++i){
		cout << i << " ";
	}
	cout << endl;
	int y; cin >> y;
	if(y == hi-lo+1+(int)used.size()){
		for(int i = lo; i <= hi; ++i){
			used.push_back(i);
		}
		return;
	}
	if(lo == hi || y == 1){
		for(int i = lo; i <= hi; ++i){
			unused.push_back(i);
		}
		return;
	}
	find(lo, (lo+hi)/2);
	find((lo+hi)/2+1, hi);
}

int main(){
	int n; cin >> n;
	output.resize(n);
	cout << n << " ";
	for(int i = 1; i <= n; ++i){
		cout << i << " ";
	}
	cout << endl;
	int x; cin >> x;
	if(x == n){
		cout << 0 << " ";
		for(int i = 1; i <= n; ++i){
			cout << i << " ";
		}
		cout << endl;
		return 0;
	}
	if(x == 1){
		cout << "0 ";
		for(int i = 0; i < n; ++i){
			cout << "1 ";
		}
		cout << endl;
		return 0;
	}
	int hi = n;
	while(x != hi){
		k++;
		hi/=2;
		cout << hi << " ";
		for(int i = 1; i <= hi; ++i){
			cout << i << " ";
		}
		cout << endl;
		cin >> x;
	}
	for(int i = 1; i <= hi; ++i){
		used.push_back(i);
	}
	find(hi+1, n);
	for(int i = 0; i < (int)used.size(); ++i){
		output[used[i]-1] = i+1;
	}
	for(int i = 0; i < (int)unused.size(); ++i){
		find2(0,(int)used.size()-1,unused[i]);
	}
	cout << "0 ";
	for(int i : output){
		cout << i << " ";
	}
	cout << endl;
}

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