Submission #160076

#	Time	Username	Problem	Language	Result	Execution time	Memory
160076		Leonardo_Paes	Carnival (CEOI14_carnival)	C++11	100 / 100	21 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){
	printf("%d", rep.size() + 1);
	for(int i=0; i<rep.size(); i++) printf(" %d", rep[i]);
	cout << " " << u << endl;
	int x;
	scanf("%d", &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(){
    scanf("%d", &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;

    printf("%d", 0);

   	for(int i=1; i<=n; i++) printf(" %d", ans[find(i)]);

   	cout << endl;

    return 0;
}

Compilation message (stderr)

carnival.cpp: In function 'int query(const std::vector<int>&, int)':
carnival.cpp:23:29: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::vector<int>::size_type {aka long unsigned int}' [-Wformat=]
  printf("%d", rep.size() + 1);
               ~~~~~~~~~~~~~~^
carnival.cpp:24:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<rep.size(); i++) printf(" %d", 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));
         ~~~~~~~~~~~~~~^~~~~~~~~~~~~
carnival.cpp: In function 'int query(const std::vector<int>&, int)':
carnival.cpp:27:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &x);
  ~~~~~^~~~~~~~~~
carnival.cpp: In function 'int main()':
carnival.cpp:48:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~

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