oj.uz

Submission #70394

# Submission time Handle Problem Language Result Execution time Memory
70394 2018-08-22T19:13:43 Z spencercompton Carnival (CEOI14_carnival) C++17
100 / 100
 25 ms 700 KB 
#include <bits/stdc++.h>
using namespace std;

bool query(vector<int> li){
	cout << li.size();
	for(int i = 0; i<li.size(); i++){
		cout << " " << (li[i]+1);
	}
	cout << endl;
	int x;
	cin >> x;
	return x<li.size();
}
vector<int> sub(vector<int> a, int l, int r){
	vector<int> ret;
	for(int i = l; i<=r; i++){
		ret.push_back(a[i]);
	}
	return ret;
}
vector<int> comp[150];
int id[150];
int sz[150];
int main(){
	int n;
	cin >> n;
	vector<int> all;
	for(int i = 0; i<n; i++){
		all.push_back(i);
		id[i] = i;
		sz[i] = 1;
		comp[i].push_back(i);
	}
	while(query(all)){
		int lo = 0;
		int hi = all.size()-1;
		while(lo<hi){
			int mid = (lo+hi)/2;
			if(query(sub(all,0,mid))){
				hi = mid;
			}
			else{
				lo = mid+1;
			}
		}
		int en = lo;
		lo = 0;
		hi = en;
		while(lo<hi){
			int mid = (lo+hi+1)/2;
			if(query(sub(all,mid,en))){
				lo = mid;
			}
			else{
				hi = mid-1;
			}
		}
		int a = all[lo];
		int b = all[en];
		int ca = id[a];
		int cb = id[b];
		for(int i = 0; i<comp[ca].size(); i++){
			comp[cb].push_back(comp[ca][i]);
			id[comp[ca][i]] = cb;
			sz[cb]++;
		}
		comp[ca].clear();
		vector<int> nex;
		for(int i = 0; i<all.size(); i++){
			if(i==en){
				continue;
			}
			nex.push_back(all[i]);
		}
		all = nex;
	}
	map<int, int> ma;
	int point = 1;
	for(int i = 0; i<n; i++){
		if(ma.find(id[i])==ma.end()){
			ma[id[i]] = point++;
		}
	}
	cout << 0;
	for(int i = 0; i<n; i++){
		cout << " " << ma[id[i]];
	}
	cout << endl;
}

Compilation message

carnival.cpp: In function 'bool query(std::vector<int>)':
carnival.cpp:7:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i<li.size(); i++){
                 ~^~~~~~~~~~
carnival.cpp:13:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  return x<li.size();
         ~^~~~~~~~~~
carnival.cpp: In function 'int main()':
carnival.cpp:63:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i<comp[ca].size(); i++){
                  ~^~~~~~~~~~~~~~~~
carnival.cpp:70:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i<all.size(); i++){
                  ~^~~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 296 KB Output is correct
2 Correct 15 ms 440 KB Output is correct
3 Correct 8 ms 440 KB Output is correct
4 Correct 3 ms 548 KB Output is correct
5 Correct 14 ms 548 KB Output is correct
6 Correct 14 ms 548 KB Output is correct
7 Correct 13 ms 644 KB Output is correct

Subtask #2
20.0 / 20.0

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

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 644 KB Output is correct
2 Correct 10 ms 644 KB Output is correct
3 Correct 15 ms 644 KB Output is correct
4 Correct 3 ms 644 KB Output is correct
5 Correct 14 ms 644 KB Output is correct
6 Correct 11 ms 644 KB Output is correct
7 Correct 20 ms 644 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 644 KB Output is correct
2 Correct 23 ms 644 KB Output is correct
3 Correct 12 ms 644 KB Output is correct
4 Correct 3 ms 700 KB Output is correct
5 Correct 25 ms 700 KB Output is correct
6 Correct 12 ms 700 KB Output is correct
7 Correct 19 ms 700 KB Output is correct

Subtask #5
20.0 / 20.0

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