Submission #25949

#	Time	Username	Problem	Language	Result	Execution time	Memory
25949		kdh9949	Carnival (CEOI14_carnival)	C++14	100 / 100	16 ms	2024 KiB

carnival

#include <bits/stdc++.h>
using namespace std;

int n, p[151];

int fnd(int x){ return p[x] = (x == p[x] ? x : fnd(p[x])); }
void uni(int x, int y){ p[fnd(x)] = fnd(y); }

vector<int> f(int s, int e){
	if(s == e){
		vector<int> ret; ret.push_back(s);
		return ret;
	}
	vector<int> l = f(s, (s + e) / 2);
	vector<int> r = f((s + e) / 2 + 1, e);
	int rs = r.size();
	vector<int> ret;
	for(auto &i : l){
		printf("%d %d ", rs + 1, i);
		for(auto &j : r) printf("%d ", j);
		fflush(stdout);
		int t; scanf("%d", &t);
		if(t == rs + 1){
			ret.push_back(i);
			continue;
		}
		int s = 0, e = r.size() - 1;
		while(s < e){
			int m = (s + e) / 2;
			printf("%d %d ", m - s + 2, i);
			for(int j = s; j <= m; j++) printf("%d ", r[j]);
			fflush(stdout);
			scanf("%d", &t);
			if(t < m - s + 2) e = m;
			else s = m + 1;
		}
		uni(i, r[s]);
	}
	for(auto &i : r) ret.push_back(i);
	return ret;
}

int main(){
	scanf("%d", &n);
	for(int i = 1; i <= n; i++) p[i] = i;
	f(1, n);
	set<int> ss;
	int cnt = 0, c[151];
	for(int i = 1; i <= n; i++){
		if(ss.find(fnd(i)) != ss.end()) continue;
		ss.insert(fnd(i));
		c[fnd(i)] = ++cnt;
	}
	printf("0 ");
	for(int i = 1; i <= n; i++)	printf("%d ", c[fnd(i)]);
	fflush(stdout);
}

Compilation message (stderr)

carnival.cpp: In function 'std::vector<int> f(int, int)':
carnival.cpp:22:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int t; scanf("%d", &t);
                         ^
carnival.cpp:33:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &t);
                   ^
carnival.cpp: In function 'int main()':
carnival.cpp:44:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
                 ^

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