Submission #63068

#	Time	Username	Problem	Language	Result	Execution time	Memory
63068		IvanC	Carnival (CEOI14_carnival)	C++17	100 / 100	12 ms	592 KiB

carnival

#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;

}

Compilation message (stderr)

carnival.cpp: In function 'int divide_and_conquer(std::vector<int>, int)':
carnival.cpp:37:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0;i<T.size();i++){
                ~^~~~~~~~~
carnival.cpp:43:8: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if(sz == firstHalf.size()) return divide_and_conquer(firstHalf,target);
     ~~~^~~~~~~~~~~~~~~~~~~
carnival.cpp: In function 'int main()':
carnival.cpp:62:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(doQuery(T,i) == T.size() + 1){
      ~~~~~~~~~~~~~^~~~~~~~~~~~~~~

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