Submission #818924

#	Time	Username	Problem	Language	Result	Execution time	Memory
818924		Faisal_Saqib	Carnival (CEOI14_carnival)	C++17	100 / 100	7 ms	336 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 of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |  for(int i = 0;i<T.size();i++){
      |                ~^~~~~~~~~
carnival.cpp:43:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |  if(sz == firstHalf.size()) return divide_and_conquer(firstHalf,target);
      |     ~~~^~~~~~~~~~~~~~~~~~~
carnival.cpp: In function 'int main()':
carnival.cpp:62:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |   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