Submission #534656

#	Time	Username	Problem	Language	Result	Execution time	Memory
534656		shrimb	Carnival (CEOI14_carnival)	C++17	100 / 100	10 ms	328 KiB

carnival

#include"bits/stdc++.h"
#define int long long
// #define endl '\n'
using namespace std;

int dsu[2000001];
int ans[2000001];

int Find (int x) {
	return dsu[x] == x ? x : dsu[x] = Find(dsu[x]);
}

void Union (int a, int b) {
	dsu[Find(a)] = Find(b);
}

int Query (vector<int> v, int x) {
	cout << v.size() + 1 << " ";
	for (int i : v) cout << i << " ";
	cout << x;
	cout << endl;
	int X;
	cin >> X;
	return X;
}


signed main () {

	int n;
	cin >> n;
	vector<int> num;
	for (int i = 1 ; i <= n ; i++) dsu[i] = i;
	num = {1};
	for (int i = 2 ; i <= n ; i++) {
		// cerr << "Query: " << Query(num, i) << endl;
		if (Query(num, i) == num.size() + 1) num.push_back(i);
		else {
			int l = 0, r = num.size() - 1;
			while (r > l) {
				int m = (l + r) / 2;
				if (Query(vector<int>(num.begin() + l, num.begin() + m + 1), i) == m - l + 1) {
					r = m;

				} else l = m + 1;
			}
			Union(num[l], i);
		}
	}
	// cerr << "dbg: ";
	// for (int i : num) cout << i << " ";
	// cout << endl;
	int c = 1;
	for (int i = 1 ; i <= n ; i++) if (dsu[i] == i) ans[i] = c++;
	cout << 0 << " ";
	for (int i = 1 ; i <= n ; i++) cout << ans[Find(i)] << " ";
}

Compilation message (stderr)

carnival.cpp: In function 'int main()':
carnival.cpp:38:21: 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]
   38 |   if (Query(num, i) == num.size() + 1) num.push_back(i);
      |       ~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~

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