oj.uz

Submission #769178

# Submission time Handle Problem Language Result Execution time Memory
769178 2023-06-29T09:28:25 Z raysh07 Carnival (CEOI14_carnival) C++17
100 / 100
 22 ms 324 KB 
#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

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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 208 KB Output is correct
2 Correct 13 ms 320 KB Output is correct
3 Correct 8 ms 312 KB Output is correct
4 Correct 5 ms 208 KB Output is correct
5 Correct 19 ms 300 KB Output is correct
6 Correct 21 ms 208 KB Output is correct
7 Correct 15 ms 324 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 208 KB Output is correct
2 Correct 10 ms 312 KB Output is correct
3 Correct 6 ms 208 KB Output is correct
4 Correct 6 ms 324 KB Output is correct
5 Correct 21 ms 208 KB Output is correct
6 Correct 19 ms 208 KB Output is correct
7 Correct 15 ms 208 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 320 KB Output is correct
2 Correct 20 ms 208 KB Output is correct
3 Correct 14 ms 208 KB Output is correct
4 Correct 5 ms 324 KB Output is correct
5 Correct 19 ms 308 KB Output is correct
6 Correct 18 ms 208 KB Output is correct
7 Correct 13 ms 208 KB Output is correct

Subtask #4
20.0 / 20.0

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

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 300 KB Output is correct
2 Correct 17 ms 208 KB Output is correct
3 Correct 9 ms 208 KB Output is correct
4 Correct 11 ms 304 KB Output is correct
5 Correct 12 ms 208 KB Output is correct
6 Correct 9 ms 208 KB Output is correct
7 Correct 6 ms 320 KB Output is correct