Submission #476241

#	Time	Username	Problem	Language	Result	Execution time	Memory
476241		Hamed5001	Carnival (CEOI14_carnival)	C++14	0 / 100	1 ms	200 KiB

carnival

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int mxN = 150;
vector<int> ans(mxN);

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 get_parent(int a) {
		return P[a] = (P[a] == a ? a : get_parent(P[a]));
	}

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

DSU d(mxN);

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

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

	ans[0] = id++;

	for (int i = 1; i < N; i++) {
		if (query(0, i-1, i)) {
			ans[i] = id++;
			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;
		}
		ans[i] = ans[l];
		d.unite(i, l);
	}

	cout << 0 << ' ';
	for (int i = 0; i < N; i++)
		cout << ans[i] << ' ';
	cout << endl;
}

int main() {
	
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	solve();
	return 0;
}

Compilation message (stderr)

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

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