oj.uz

Submission #920180

# Submission time Handle Problem Language Result Execution time Memory
920180 2024-02-02T08:10:09 Z oblantis Carnival (CEOI14_carnival) C++17
100 / 100
 7 ms 556 KB 
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define all(v) v.begin(), v.end()
#define pb push_back
#define ss second
#define ff first
#define vt vector
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef pair<int, int> pii;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
const int inf = 1e9;
const int mod = 1e9+7;
const int maxn = 1e6 + 1;

int x;
void ask(int l, int r){
	cout << r - l + 1 << ' ';
	while(l <= r){
		cout << l << ' ';
		l++;
	}
	cout << endl;
	cin >> x;
}
void solve() {
	int n;
	cin >> n;
	int l[n + 1];
	l[0] = 0;
	vt<int> unq;
	unq.pb(0);
	for(int i = 1; i <= n; i++){
		int xl = 0, xr = unq.size();
		while(xl + 1 < xr){
			int mid = (xl + xr) / 2;
			ask(unq[mid], i);
			for(int j = unq[mid]; j < i; j++){
				if(l[j] < unq[mid])x--;
			}
			if(x)xr = mid;
			else xl = mid;
		}
		l[i] = unq[xl];
		if(l[i] == 0){
			unq.pb(i);
		}
		else unq.erase(unq.begin() + xl), unq.pb(i);
	}
	cout << 0 << ' ';
	for(int i = 1, cnt = 1; i <= n; i++){
		if(l[i] == 0)l[i] = cnt++;
		else l[i] = l[l[i]];
		cout << l[i] << ' ';
	}
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int times = 1;
	//cin >> times;
	for(int i = 1; i <= times; i++) {
		solve();
	}
	return 0;
}

Subtask #1
20.0 / 20.0

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

Subtask #2
20.0 / 20.0

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

Subtask #3
20.0 / 20.0

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

Subtask #4
20.0 / 20.0

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

Subtask #5
20.0 / 20.0

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