Central-European Olympiad in Informatics 2014

carnival.cpp

// Ivan Carvalho
// Carnival - CEOI 2014
// O(N*log(N))
#include <bits/stdc++.h>
using namespace std;
 
const int MAXN = 160;
 
int pai[MAXN],qualcor[MAXN],N,ultima_cor;
 
int find(int x){
	if(x == pai[x]) return x;
	return pai[x] = find(pai[x]);
}
 
void join(int x,int y){
	x = find(x);
	y = find(y);
	if(x == y) return;
	if(x > y) swap(x,y);
	pai[y] = x;
}
 
int doQuery(vector<int> L,int v){
	L.push_back(v);
	cout << L.size();
	for(int i : L) cout << " " << i;
	cout << endl;
	int ans;
	cin >> ans;
	return ans;
}
 
int divide_and_conquer(vector<int> T,int target){
	if(T.size() == 1) return T[0];
 
	int mid = T.size()/2;
 
	vector<int> firstHalf,lastHalf;
	for(int i = 0;i<T.size();i++){
		if(i < mid) firstHalf.push_back(T[i]);
		else lastHalf.push_back(T[i]);
	}
 
	int sz = doQuery(firstHalf,target); 
	if(sz == firstHalf.size()) return divide_and_conquer(firstHalf,target);
	else return divide_and_conquer(lastHalf,target);
 
}
 
int main(){
 
	int N;
	cin >> N;
 
	for(int i = 1;i<=N;i++){
		pai[i] = i;
	}
 
	for(int i = 2;i<=N;i++){
 
		vector<int> T;
		for(int j = 1;j < i;j++) if(find(j) == j) T.push_back(j);
 
		if(doQuery(T,i) == T.size() + 1){
			continue;
		}
 
		int k = divide_and_conquer(T,i);
		join(k,i);
 
	}
 
	for(int i = 1;i<=N;i++){
		if(find(i) == i) qualcor[i] = ++ultima_cor;
	}
 
	cout << 0;
	for(int i = 1 ;i <= N;i++){
		cout << " " << qualcor[find(i)];
	}
 
	cout << endl;
 
}