oj.uz

Submission #750529

# Submission time Handle Problem Language Result Execution time Memory
750529 2023-05-29T15:57:41 Z vjudge1 Carnival (CEOI14_carnival) C++17
100 / 100
 9 ms 336 KB 
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include "tools.h"
#define debug(x...) cerr << "\033[1;31m"<<__func__<<"():"<<__LINE__<<" [" << #x << "] = ["; _print(x); cerr << "\033[0m" << endl;
#else
#define debug(x...)
#endif

using ull = unsigned long long;
using ll = long long;
using db = double;
using str = string;
using pi = pair<int, int>;
using pl = pair<ll, ll>;
using pd = pair<db, db>;

#define mp make_pair
#define fi first
#define se second
#define sz(x) int((x).size())
#define all(x) (x).begin(), (x).end()
#define rsz resize
#define ins insert
#define pb push_back
#define eb emplace_back
#define lb lower_bound
#define ub upper_bound
#define each(i, v) for(auto &i : v)

const int MOD = (int)1e9+7; // 998244353
const int NM = (int)2e5+5; // 1e6+5;
const int INF = (int)1e9+7;
const ll INF_LL = (ll)1e18+7;
const db PI = acos((db) - 1);

int lg2(ull i) { return i ? __builtin_clzll(1) - __builtin_clzll(i) : -1; }

int ask(vector<int> a, int check){
	cout << sz(a) + 1;
	for (int i : a) cout << " " << i;
	cout << " " << check;
	cout << endl;
	int resp; cin >> resp;
	return resp;
}

vector<int> p;

int get(int x){
	return x == p[x] ? x : p[x] = get(p[x]);
}

bool unite(int x, int y){
	x = get(x);
	y = get(y);
	if (x == y) return false;
	p[y] = x;
	return true;
}


void solve(){
	int n;
	cin >> n;
	p.resize(n + 1);
	iota(all(p), 0);
	vector<int> heads;
	for (int i = 2; i <= n; i++){
		heads.clear();
		for (int j = 1; j < i; j++){
			if (get(j) == j) heads.eb(j);
		}
		if (ask(heads, i) == sz(heads) + 1) continue;
		int l = 0, r = sz(heads) - 1;
		while(l < r){
			int m = (l + r) >> 1;
			if (ask(vector<int>(heads.begin() + l, heads.begin() + m + 1), i) == m - l + 1){
				r = m;
			}else{
				l = m + 1;
			}
		}
		unite(heads[l], i);
	}
	vector<int> res(n + 1);
	int t = 1;
	for (int i = 1; i <= n; i++){
		if (get(i) == i) res[i] = t++;
	}
	cout << 0;
	for (int i = 1; i <= n; i++){
		cout << " " << res[get(i)];
	}
	cout << endl;
}

int main() {
#ifdef LOCAL
	clock_t __START_CLOCK = clock();
#endif
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	int tc = 1; // cin >> tc;
	while(tc--) {
		solve();
	}

#ifdef LOCAL
	cerr << "\033[1;33m"<< (clock() - __START_CLOCK) / CLOCKS_PER_SEC << " s\033[0m" << endl;
#endif
	return 0;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 208 KB Output is correct
2 Correct 6 ms 208 KB Output is correct
3 Correct 5 ms 336 KB Output is correct
4 Correct 5 ms 208 KB Output is correct
5 Correct 4 ms 208 KB Output is correct
6 Correct 3 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 5 ms 208 KB Output is correct
2 Correct 6 ms 208 KB Output is correct
3 Correct 3 ms 208 KB Output is correct
4 Correct 4 ms 324 KB Output is correct
5 Correct 5 ms 208 KB Output is correct
6 Correct 6 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 7 ms 208 KB Output is correct
3 Correct 8 ms 312 KB Output is correct
4 Correct 2 ms 316 KB Output is correct
5 Correct 6 ms 316 KB Output is correct
6 Correct 7 ms 312 KB Output is correct
7 Correct 8 ms 208 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 5 ms 208 KB Output is correct
3 Correct 3 ms 320 KB Output is correct
4 Correct 3 ms 208 KB Output is correct
5 Correct 9 ms 208 KB Output is correct
6 Correct 5 ms 208 KB Output is correct
7 Correct 7 ms 208 KB Output is correct

Subtask #5
20.0 / 20.0

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