Submission #769178

#	Time	Username	Problem	Language	Result	Execution time	Memory
769178		raysh07	Carnival (CEOI14_carnival)	C++17	100 / 100	22 ms	324 KiB

carnival

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF (int)1e18
#define f first
#define s second

mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());

struct ufds{
	vector <int> root, sz;
	int n;

	void init(int nn){
		n = nn;
		root.resize(n + 1);
		sz.resize(n + 1, 1);
		for (int i = 1; i <= n; i++) root[i] = i;
	}

	int find(int x){
		if (root[x] == x) return x;
		return root[x] = find(root[x]);
	}

	bool unite(int x, int y){
		x = find(x); y = find(y);
		if (x == y) return false;

		if (y < x) swap(x, y);
		sz[x] += sz[y];
		root[y] = x;
		return true;
	}
};

int query(vector <int> a){
	int cnt = 0;
	for (auto x : a) cnt += x;

	cout << cnt;
	for (int i = 0; i < a.size(); i++){
		if (a[i] == 1) cout << " " << i + 1;
	}
	cout << endl;
	int x; cin >> x;
	return x;
}

bool check(int i, int j, int n){
	vector <int> a(n, 0);
	for (int k = i; k <= j; k++) a[k] = 1;

	int v1 = query(a);
	a[i] = 0;
	int v2 = query(a);

	return v1 == v2;
}

void Solve()
{
	int n; cin >> n;
	ufds uf;
	uf.init(n);

	for (int i = 0; i < n - 1; i++){
		if (check(i, n - 1, n)){
			int lo = i + 1;
			int hi = n - 1;

			while (lo != hi){
				int mid = (lo + hi) / 2;

				if (check(i, mid, n)) hi = mid;
				else lo = mid + 1;
			}

			//cout << "ADDED " << i + 1 << " " << lo + 1 << "\n";
			uf.unite(i + 1, lo + 1);
		}
	}

	vector <int> ok(n + 1);
	int cnt = 0;
	for (int i = 1; i <= n; i++){
		if (uf.find(i) == i){
			ok[i] = ++cnt;
		}
	}

	cout << 0;
	for (int i = 0; i < n; i++) cout << " " << ok[uf.find(i + 1)];
	cout << endl;
}

int32_t main() 
{
    auto begin = std::chrono::high_resolution_clock::now();
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t = 1;
  //  cin >> t;
    for(int i = 1; i <= t; i++) 
    {
        //cout << "Case #" << i << ": ";
        Solve();
    }
    auto end = std::chrono::high_resolution_clock::now();
    auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
    cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n"; 
    return 0;
}

Compilation message (stderr)

carnival.cpp: In function 'long long int query(std::vector<long long int>)':
carnival.cpp:42:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |  for (int i = 0; i < a.size(); i++){
      |                  ~~^~~~~~~~~~

• Subtask 1: 20 / 20
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 20 / 20
• Subtask 5: 20 / 20