oj.uz

Submission #709993

# Submission time Handle Problem Language Result Execution time Memory
709993 2023-03-15T02:34:17 Z vjudge1 Carnival (CEOI14_carnival) C++17
100 / 100
 14 ms 304 KB 
#include <bits/stdc++.h>
using namespace std;

void main_program();

signed main(){
	main_program();
}

int ask(vector<int> &V){
	if (V.empty()) return 0;
	cout << V.size();
	for (auto i: V) cout << " " << i+1;
	cout << "\n"; cout.flush();
	int res; cin >> res; return res;
}

void main_program(){
	int n; cin >> n;

	int prev = 0;
	vector<int> query = {};
	vector<int> f = {};

	for (int i = 0; i < n; i++){
		query.push_back(i);
		int val = ask(query);

		if (val > prev){
			f.push_back(i);
			prev = val;
		}
	}

	vector<int> arrow(n, -2);
	for (auto i: f) arrow[i] = -1;

	for (int i = 0; i < n; i++){
		if (arrow[i] != -2) continue;
		int l = 0, r = f.size() - 1;
		while (l < r){
			int mid = (l + r) >> 1;

			vector<int> query2;
			for (int j = 0; j <= mid; j++) query2.push_back(f[j]);
			query2.push_back(i);

			sort(query2.begin(), query2.end());

			if (ask(query2) == (int)query2.size()) l = mid+1;
			else r = mid;
		}
		arrow[i] = f[l];
	}

	vector<int> num(n, 0);
	for (int i = 0; i < (int)f.size(); i++) num[f[i]] = i+1;

	for (int i = 0; i < n; i++){
		if (!num[i]) num[i] = num[arrow[i]];
	}

	cout << 0;
	for (int i = 0; i < n; i++) cout << " " << num[i];
	cout << "\n"; cout.flush();
}

Subtask #1
20.0 / 20.0

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

Subtask #2
20.0 / 20.0

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

Subtask #3
20.0 / 20.0

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

Subtask #4
20.0 / 20.0

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

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 300 KB Output is correct
2 Correct 6 ms 304 KB Output is correct
3 Correct 7 ms 208 KB Output is correct
4 Correct 9 ms 208 KB Output is correct
5 Correct 8 ms 208 KB Output is correct
6 Correct 7 ms 208 KB Output is correct
7 Correct 4 ms 296 KB Output is correct