oj.uz

Submission #551344

# Submission time Handle Problem Language Result Execution time Memory
551344 2022-04-20T13:05:23 Z AugustinasJucas Carnival (CEOI14_carnival) C++14
100 / 100
 16 ms 312 KB 
#include <bits/stdc++.h>
using namespace std;
const int dydis = 151;
int type[dydis];
int n;
int ask(vector<int> vec) {
	cout << vec.size() << " ";
	for(auto &x : vec) cout << x+1 << " ";
	cout << endl; 
	int ans;
	cin >> ans;
	return ans;
}
int tevas[dydis];
int fp(int v) {
	if(tevas[v] == v) return v;
	return tevas[v] = fp(tevas[v]);
}
void merge(int a, int b) {
	a = fp(a);
	b = fp(b);
	tevas[a] = b;
}
vector<int> prm(int i1, vector<int> a) {
	vector<int> ret;
	for(int i = 0; i <= i1; i++) ret.push_back(a[i]);
	return ret;
}
void compTevas(){
	vector<int> visi;
	for(int i = 0; i < n; i++) {
		if(fp(i) == i) visi.push_back(i);
	}
	sort(visi.begin(), visi.end());
	for(int i = 0; i < n; i++) {
		type[i] = lower_bound(visi.begin(), visi.end(), fp(i)) - visi.begin();
	}
} 
int main () {
	for(int i = 0; i < dydis; i++) tevas[i] = i;
	cin >> n;
	for(int i = 0; i < n; i++) type[i] = -1;
	
	vector<int> list;
	for(int i = 0; i < n; i++) {
		list.push_back(i);
	}
	
	while(list.size()) {
		int i1 = list.size();
		int l = 0; int r = list.size()-1; int mid;
		while(l <= r) {
			mid = (l + r) / 2;
			if(ask(prm(mid, list)) != mid+1) {	
				r = mid-1;
				i1 = mid;
			}else {
				l = mid+1;
			}
		}
		if(i1 == (int)list.size()) break;
		l = 0; r = i1; 
		int i2 = -1;
		while(l <= r) {
			mid = (l + r) / 2;
			vector<int> visi;
			for(int j = mid; j <= i1; j++) visi.push_back(list[j]);
			if(ask(visi) == i1 - mid + 1) {
				r = mid-1;
			}else {
				l = mid+1;
				i2 = mid;
			}
		}
		merge(list[i1], list[i2]);
		list.erase(list.begin()+i1);
	}
	
	compTevas();
	
	cout << "0 ";
	for(int i = 0; i < n; i++) {
		cout << type[i] + 1 << " ";
	}
	cout << endl;
	
	
	return 0;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 304 KB Output is correct
2 Correct 15 ms 208 KB Output is correct
3 Correct 7 ms 308 KB Output is correct
4 Correct 2 ms 304 KB Output is correct
5 Correct 10 ms 208 KB Output is correct
6 Correct 6 ms 208 KB Output is correct
7 Correct 15 ms 304 KB Output is correct

Subtask #2
20.0 / 20.0

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

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 208 KB Output is correct
2 Correct 12 ms 208 KB Output is correct
3 Correct 13 ms 312 KB Output is correct
4 Correct 2 ms 208 KB Output is correct
5 Correct 12 ms 308 KB Output is correct
6 Correct 12 ms 208 KB Output is correct
7 Correct 16 ms 312 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 308 KB Output is correct
2 Correct 11 ms 208 KB Output is correct
3 Correct 6 ms 304 KB Output is correct
4 Correct 1 ms 208 KB Output is correct
5 Correct 14 ms 208 KB Output is correct
6 Correct 11 ms 304 KB Output is correct
7 Correct 14 ms 208 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 208 KB Output is correct
2 Correct 16 ms 308 KB Output is correct
3 Correct 10 ms 208 KB Output is correct
4 Correct 12 ms 308 KB Output is correct
5 Correct 9 ms 208 KB Output is correct
6 Correct 9 ms 296 KB Output is correct
7 Correct 3 ms 208 KB Output is correct