oj.uz

Submission #304738

# Submission time Handle Problem Language Result Execution time Memory
304738 2020-09-21T19:56:44 Z sofapuden Carnival (CEOI14_carnival) C++14
100 / 100
 14 ms 384 KB 
#include <bits/stdc++.h>

using namespace std;

vector<int> used;
vector<int> unused;
vector<int> output;
int k = 0;

int find2(int lo, int hi, int target){
	int x;
	cout << hi-lo+2 << " ";
	for(int i = lo; i <= hi; ++i){
		cout << used[i] << " ";
	}
	cout << target << endl;
	cin >> x;
	if(x == hi-lo+2)return -1;
	if(hi == lo){
		output[target-1] = output[used[hi]-1];
		return hi;
	}
	int y = find2(lo, (lo+hi)/2, target);
	if(y != -1)return y;
	else return find2((lo+hi)/2+1, hi, target);
}
		

void find(int lo, int hi){
	k++;
	cout << hi-lo+1+(int)used.size() << " ";
	for(int i = 0; i < (int)used.size(); ++i){
		cout << used[i] << " ";
	}
	for(int i = lo; i <= hi; ++i){
		cout << i << " ";
	}
	cout << endl;
	int y; cin >> y;
	if(y == hi-lo+1+(int)used.size()){
		for(int i = lo; i <= hi; ++i){
			used.push_back(i);
		}
		return;
	}
	if(lo == hi || y == 1){
		for(int i = lo; i <= hi; ++i){
			unused.push_back(i);
		}
		return;
	}
	find(lo, (lo+hi)/2);
	find((lo+hi)/2+1, hi);
}

int main(){
	int n; cin >> n;
	output.resize(n);
	cout << n << " ";
	for(int i = 1; i <= n; ++i){
		cout << i << " ";
	}
	cout << endl;
	int x; cin >> x;
	if(x == n){
		cout << 0 << " ";
		for(int i = 1; i <= n; ++i){
			cout << i << " ";
		}
		cout << endl;
		return 0;
	}
	if(x == 1){
		cout << "0 ";
		for(int i = 0; i < n; ++i){
			cout << "1 ";
		}
		cout << endl;
		return 0;
	}
	int hi = n;
	while(x != hi){
		k++;
		hi/=2;
		cout << hi << " ";
		for(int i = 1; i <= hi; ++i){
			cout << i << " ";
		}
		cout << endl;
		cin >> x;
	}
	for(int i = 1; i <= hi; ++i){
		used.push_back(i);
	}
	find(hi+1, n);
	for(int i = 0; i < (int)used.size(); ++i){
		output[used[i]-1] = i+1;
	}
	for(int i = 0; i < (int)unused.size(); ++i){
		find2(0,(int)used.size()-1,unused[i]);
	}
	cout << "0 ";
	for(int i : output){
		cout << i << " ";
	}
	cout << endl;
}

Subtask #1
20.0 / 20.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 256 KB Output is correct
2 Correct 13 ms 256 KB Output is correct
3 Correct 4 ms 256 KB Output is correct
4 Correct 3 ms 256 KB Output is correct
5 Correct 9 ms 376 KB Output is correct
6 Correct 10 ms 256 KB Output is correct
7 Correct 11 ms 256 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 10 ms 256 KB Output is correct
3 Correct 12 ms 256 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 11 ms 256 KB Output is correct
6 Correct 11 ms 256 KB Output is correct
7 Correct 12 ms 256 KB Output is correct

Subtask #4
20.0 / 20.0

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

Subtask #5
20.0 / 20.0

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