oj.uz

Submission #160075

# Submission time Handle Problem Language Result Execution time Memory
160075 2019-10-25T21:49:27 Z Leonardo_Paes Carnival (CEOI14_carnival) C++11
100 / 100
 15 ms 404 KB 
#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

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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 376 KB Output is correct
2 Correct 9 ms 248 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 5 ms 252 KB Output is correct
5 Correct 6 ms 248 KB Output is correct
6 Correct 5 ms 248 KB Output is correct
7 Correct 11 ms 248 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 252 KB Output is correct
2 Correct 15 ms 248 KB Output is correct
3 Correct 6 ms 248 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Correct 5 ms 248 KB Output is correct
6 Correct 6 ms 376 KB Output is correct
7 Correct 5 ms 376 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 8 ms 248 KB Output is correct
3 Correct 10 ms 248 KB Output is correct
4 Correct 4 ms 396 KB Output is correct
5 Correct 8 ms 376 KB Output is correct
6 Correct 8 ms 376 KB Output is correct
7 Correct 6 ms 248 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 376 KB Output is correct
2 Correct 5 ms 248 KB Output is correct
3 Correct 7 ms 248 KB Output is correct
4 Correct 5 ms 248 KB Output is correct
5 Correct 14 ms 248 KB Output is correct
6 Correct 12 ms 376 KB Output is correct
7 Correct 11 ms 376 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 248 KB Output is correct
2 Correct 10 ms 376 KB Output is correct
3 Correct 9 ms 248 KB Output is correct
4 Correct 8 ms 248 KB Output is correct
5 Correct 8 ms 248 KB Output is correct
6 Correct 7 ms 404 KB Output is correct
7 Correct 6 ms 248 KB Output is correct