oj.uz

Submission #779804

# Submission time Handle Problem Language Result Execution time Memory
779804 2023-07-11T21:46:24 Z NK_ Carnival (CEOI14_carnival) C++17
100 / 100
 15 ms 444 KB 
// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>

using namespace std;

#define nl '\n'

template<class T> using V = vector<T>;
int main() {
	cin.tie(0)->sync_with_stdio(0);
	
	int N; cin >> N;
	V<int> P(N, -1);

	map<pair<int, int>, int> ASK;

	auto ask = [&](int x, int l, int r) {
		pair<int, int> q = make_pair(l, r);

		int res1;
		if (ASK.find(q) == ASK.end()) {
			cout << r - l + 1 << " ";
			for(int i = l; i <= r; i++) cout << " " << i + 1;
			cout << endl;

			cin >> res1; // WITHOUT
			ASK[q] = res1;
		} else res1 = ASK[q];

		cout << r - l + 1 + 1 << " " << x + 1;
		for(int i = l; i <= r; i++) cout << " " << i + 1;
		cout << endl;
	
		int res2; cin >> res2; // WITH

		return res1 == res2;
	};

	for(int i = 0; i < N; i++) {
		int lo = i, hi = N - 1;
		while(lo < hi) {
			int mid = (lo + hi + 1) / 2;
			if (ask(i, mid, hi)) lo = mid;
			else hi = mid - 1;
		}
		P[i] = lo;
	}	

	V<int> C(N, -1); int cur = 1;
	for(int i = N-1; i >= 0; i--) {
		if (C[P[i]] == -1) C[i] = cur++;
		else C[i] = C[P[i]];
	}

	cout << 0;
	for(auto x : C) cout << " " << x;
	cout << endl;

    return 0;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 208 KB Output is correct
2 Correct 10 ms 332 KB Output is correct
3 Correct 5 ms 320 KB Output is correct
4 Correct 10 ms 336 KB Output is correct
5 Correct 8 ms 208 KB Output is correct
6 Correct 8 ms 208 KB Output is correct
7 Correct 11 ms 328 KB Output is correct

Subtask #2
20.0 / 20.0

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

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 208 KB Output is correct
2 Correct 7 ms 336 KB Output is correct
3 Correct 15 ms 340 KB Output is correct
4 Correct 11 ms 340 KB Output is correct
5 Correct 8 ms 208 KB Output is correct
6 Correct 11 ms 316 KB Output is correct
7 Correct 10 ms 324 KB Output is correct

Subtask #4
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 14 ms 336 KB Output is correct
4 Correct 13 ms 332 KB Output is correct
5 Correct 11 ms 208 KB Output is correct
6 Correct 11 ms 208 KB Output is correct
7 Correct 11 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 8 ms 208 KB Output is correct
3 Correct 13 ms 336 KB Output is correct
4 Correct 6 ms 444 KB Output is correct
5 Correct 12 ms 208 KB Output is correct
6 Correct 12 ms 208 KB Output is correct
7 Correct 13 ms 332 KB Output is correct