oj.uz

Submission #63068

# Submission time Handle Problem Language Result Execution time Memory
63068 2018-07-31T15:07:35 Z IvanC Carnival (CEOI14_carnival) C++17
100 / 100
 12 ms 592 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 between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0;i<T.size();i++){
                ~^~~~~~~~~
carnival.cpp:43:8: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if(sz == firstHalf.size()) return divide_and_conquer(firstHalf,target);
     ~~~^~~~~~~~~~~~~~~~~~~
carnival.cpp: In function 'int main()':
carnival.cpp:62:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(doQuery(T,i) == T.size() + 1){
      ~~~~~~~~~~~~~^~~~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 292 KB Output is correct
2 Correct 9 ms 312 KB Output is correct
3 Correct 5 ms 456 KB Output is correct
4 Correct 6 ms 456 KB Output is correct
5 Correct 7 ms 592 KB Output is correct
6 Correct 5 ms 592 KB Output is correct
7 Correct 12 ms 592 KB Output is correct

Subtask #2
20.0 / 20.0

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

Subtask #3
20.0 / 20.0

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

Subtask #4
20.0 / 20.0

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

Subtask #5
20.0 / 20.0

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