oj.uz

Submission #476255

# Submission time Handle Problem Language Result Execution time Memory
476255 2021-09-25T16:53:28 Z Hamed5001 Carnival (CEOI14_carnival) C++14
100 / 100
 19 ms 316 KB 
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int mxN = 150;

struct DSU {
	int N;
	vector<int> P;

	DSU(int N) : N(N) {
		P.resize(N);
		for (int i = 0; i < N; i++)
			P[i] = i;
	}

	int getParent(int a) {
		return P[a] = (P[a] == a ? a : getParent(P[a]));
	}

	void unite(int a, int b) {
		a = getParent(a);
		b = getParent(b);
		P[a] = b;
	}
};

DSU d(mxN);

bool query(int l, int r, int x) {
	set<int> st;
	st.insert(d.getParent(x));
	cout << (r-l+2) << ' ' << x+1;
	for (int i = l; i <= r; i++)
		cout << ' ' << i+1, st.insert(d.getParent(i));
	cout << endl;
	int res;
	cin >> res;
	return res == st.size();
}

int ID[mxN];

void solve() {
	int N, id = 1;
	cin >> N;	  

	for (int i = 1; i < N; i++) {
		if (query(0, i-1, i))
			continue;
		int l = 0, r = i-1, mid;
		while(l < r) {
			mid = (l+r)>>1;
			if (query(0, mid, i))
				l = mid+1;
			else
				r = mid;
		}
		d.unite(l, i);
	}
		
	vector<int> ans(N);
	for (int i = 0; i < N; i++) {
		if (!ID[d.getParent(i)])
			ID[d.getParent(i)] = id++;
		ans[i] = ID[d.getParent(i)];
	}
	cout << 0;
	for (auto &it : ans) cout << ' ' << it;
	cout << endl;
}

int main() {

	
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	solve();
	return 0;
}

Compilation message

carnival.cpp: In function 'bool query(int, int, int)':
carnival.cpp:40:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::set<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |  return res == st.size();
      |         ~~~~^~~~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 200 KB Output is correct
2 Correct 12 ms 200 KB Output is correct
3 Correct 10 ms 200 KB Output is correct
4 Correct 4 ms 308 KB Output is correct
5 Correct 9 ms 200 KB Output is correct
6 Correct 11 ms 200 KB Output is correct
7 Correct 9 ms 304 KB Output is correct

Subtask #2
20.0 / 20.0

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

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 200 KB Output is correct
2 Correct 16 ms 200 KB Output is correct
3 Correct 12 ms 200 KB Output is correct
4 Correct 7 ms 200 KB Output is correct
5 Correct 12 ms 292 KB Output is correct
6 Correct 13 ms 304 KB Output is correct
7 Correct 14 ms 200 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 200 KB Output is correct
2 Correct 15 ms 200 KB Output is correct
3 Correct 8 ms 312 KB Output is correct
4 Correct 4 ms 312 KB Output is correct
5 Correct 13 ms 300 KB Output is correct
6 Correct 9 ms 308 KB Output is correct
7 Correct 14 ms 316 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 200 KB Output is correct
2 Correct 16 ms 200 KB Output is correct
3 Correct 10 ms 200 KB Output is correct
4 Correct 9 ms 200 KB Output is correct
5 Correct 7 ms 308 KB Output is correct
6 Correct 7 ms 200 KB Output is correct
7 Correct 8 ms 200 KB Output is correct