oj.uz

Submission #534656

# Submission time Handle Problem Language Result Execution time Memory
534656 2022-03-08T13:05:52 Z shrimb Carnival (CEOI14_carnival) C++17
100 / 100
 10 ms 328 KB 
#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

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

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

Subtask #2
20.0 / 20.0

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

Subtask #3
20.0 / 20.0

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

Subtask #4
20.0 / 20.0

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

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 200 KB Output is correct
2 Correct 8 ms 200 KB Output is correct
3 Correct 7 ms 320 KB Output is correct
4 Correct 5 ms 200 KB Output is correct
5 Correct 5 ms 200 KB Output is correct
6 Correct 5 ms 328 KB Output is correct
7 Correct 4 ms 312 KB Output is correct