oj.uz

Submission #320763

# Submission time Handle Problem Language Result Execution time Memory
320763 2020-11-09T19:18:49 Z gustason Carnival (CEOI14_carnival) C++14
100 / 100
 11 ms 508 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 8 ms 384 KB Output is correct
2 Correct 7 ms 364 KB Output is correct
3 Correct 3 ms 380 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 4 ms 364 KB Output is correct
6 Correct 3 ms 492 KB Output is correct
7 Correct 7 ms 364 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 364 KB Output is correct
2 Correct 7 ms 364 KB Output is correct
3 Correct 4 ms 364 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 5 ms 364 KB Output is correct
6 Correct 5 ms 364 KB Output is correct
7 Correct 7 ms 364 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 6 ms 364 KB Output is correct
3 Correct 8 ms 364 KB Output is correct
4 Correct 3 ms 508 KB Output is correct
5 Correct 6 ms 364 KB Output is correct
6 Correct 5 ms 364 KB Output is correct
7 Correct 8 ms 364 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 364 KB Output is correct
2 Correct 4 ms 364 KB Output is correct
3 Correct 6 ms 364 KB Output is correct
4 Correct 4 ms 364 KB Output is correct
5 Correct 7 ms 364 KB Output is correct
6 Correct 6 ms 384 KB Output is correct
7 Correct 8 ms 364 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 364 KB Output is correct
2 Correct 8 ms 364 KB Output is correct
3 Correct 7 ms 364 KB Output is correct
4 Correct 11 ms 364 KB Output is correct
5 Correct 8 ms 364 KB Output is correct
6 Correct 5 ms 364 KB Output is correct
7 Correct 6 ms 360 KB Output is correct