oj.uz

Submission #160074

# Submission time Handle Problem Language Result Execution time Memory
160074 2019-10-25T21:46:17 Z Leonardo_Paes Carnival (CEOI14_carnival) C++11
100 / 100
 12 ms 380 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){
	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

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

# Verdict Execution time Memory Grader output
1 Correct 9 ms 376 KB Output is correct
2 Correct 9 ms 376 KB Output is correct
3 Correct 8 ms 248 KB Output is correct
4 Correct 4 ms 248 KB Output is correct
5 Correct 5 ms 248 KB Output is correct
6 Correct 5 ms 376 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 7 ms 248 KB Output is correct
2 Correct 10 ms 248 KB Output is correct
3 Correct 6 ms 248 KB Output is correct
4 Correct 4 ms 312 KB Output is correct
5 Correct 8 ms 248 KB Output is correct
6 Correct 7 ms 380 KB Output is correct
7 Correct 5 ms 248 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 7 ms 376 KB Output is correct
3 Correct 11 ms 248 KB Output is correct
4 Correct 6 ms 376 KB Output is correct
5 Correct 5 ms 248 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 252 KB Output is correct
2 Correct 10 ms 248 KB Output is correct
3 Correct 7 ms 248 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Correct 10 ms 376 KB Output is correct
6 Correct 12 ms 248 KB Output is correct
7 Correct 11 ms 248 KB Output is correct

Subtask #5
20.0 / 20.0

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