Submission #160078

#	Time	Username	Problem	Language	Result	Execution time	Memory
160078		Leonardo_Paes	Carnival (CEOI14_carnival)	C++11	100 / 100	11 ms	376 KiB

carnival

#include <bits/stdc++.h>

using namespace std;

const int maxn = 155;

int n, pai[maxn], siz[maxn], ans[maxn], color;

int find(int x){
	if(pai[x]==x) return x;
	return pai[x] = find(pai[x]);
}

void join(int a, int b){
	a = find(a), b = find(b);
	if(a==b) return;
	if(siz[a]<siz[b]) swap(a, b);
	pai[b] = a;
	siz[a] += siz[b];
}

int query(vector<int> const& rep, int u){
	cout << rep.size() + 1;
	for(int i=0; i<rep.size(); i++) cout << " " << rep[i];
	cout << " " << u << endl;
	int x;
	cin >> x;
	return x;
}

int dc(vector<int> const& rep, int u){
	if(rep.size()==1) return rep[0];

	int mid = rep.size()>>1;

	vector<int> half1, half2;

	for(int i=0; i<rep.size(); i++){
		if(i<mid) half1.push_back(rep[i]);
		else half2.push_back(rep[i]);
	}

	if(query(half1, u) == half1.size()) return dc(half1, u);
	return dc(half2, u);
}

int main(){
    cin >> n;

    for(int i=1; i<=n; i++) pai[i] = i, siz[i] = 1;

    for(int i=2; i<=n; i++){
    	vector<int> rep;
    	for(int j=1; j<i; j++) if(j==find(j)) rep.push_back(j);
    	if(query(rep, i) == rep.size()) join(i, dc(rep, i));
    }

    for(int i=1; i<=n; i++) if(i==find(i)) ans[i] = ++color;

    cout << 0;

   	for(int i=1; i<=n; i++) cout << " " << ans[find(i)];

   	cout << endl;

    return 0;
}

Compilation message (stderr)

carnival.cpp: In function 'int query(const std::vector<int>&, int)':
carnival.cpp:24:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<rep.size(); i++) cout << " " << rep[i];
               ~^~~~~~~~~~~
carnival.cpp: In function 'int dc(const std::vector<int>&, int)':
carnival.cpp:38:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<rep.size(); i++){
               ~^~~~~~~~~~~
carnival.cpp:43:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if(query(half1, u) == half1.size()) return dc(half1, u);
     ~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~
carnival.cpp: In function 'int main()':
carnival.cpp:55:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
      if(query(rep, i) == rep.size()) join(i, dc(rep, i));
         ~~~~~~~~~~~~~~^~~~~~~~~~~~~

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