oj.uz

Submission #25949

# Submission time Handle Problem Language Result Execution time Memory
25949 2017-06-25T07:47:05 Z kdh9949 Carnival (CEOI14_carnival) C++14
100 / 100
 16 ms 2024 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2024 KB Output is correct
2 Correct 0 ms 2024 KB Output is correct
3 Correct 3 ms 2024 KB Output is correct
4 Correct 3 ms 2024 KB Output is correct
5 Correct 0 ms 2024 KB Output is correct
6 Correct 3 ms 2024 KB Output is correct
7 Correct 16 ms 2024 KB Output is correct

Subtask #2
20.0 / 20.0

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

Subtask #3
20.0 / 20.0

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

Subtask #4
20.0 / 20.0

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

Subtask #5
20.0 / 20.0

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