oj.uz

Submission #154627

# Submission time Handle Problem Language Result Execution time Memory
154627 2019-09-23T10:40:21 Z ivandasfs Carnival (CEOI14_carnival) C++14
100 / 100
 24 ms 424 KB 
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <map>

using namespace std;

int par[155];
int pref[155];

map <int, int> M;

int find(int x) {
	if (x == par[x]) return x;
	return par[x] = find(par[x]);
}

void merge(int x, int y) {
	x = find(x);
	y = find(y);
	if (x == y) return ;
	if (rand()%2) par[x] = y;
	else par[y] = x;
}

bool check(int l, int pos) {
	int x, y;
	printf("%d ", pos-l);
	for (int i=l ; i<pos ; i++) {
		printf("%d ", i+1);
	}
	cout <<endl;
	scanf("%d", &x);
	printf("%d ", pos-l+1);
	for (int i=l ; i<=pos ; i++) {
		printf("%d ", i+1);
	}
	cout <<endl;
	scanf("%d", &y);
	if (x==y) return true;
	return false;
}

int main() {
	int n;
	scanf("%d", &n);
	for (int i=0 ; i<n ; i++) {
		par[i] = i;
	}
	pref[0] = 1;
	for (int i=1 ; i<n ; i++) {
		printf("%d ", i+1);
		for (int j=0 ; j<=i ; j++) {
			printf("%d ", j+1);
		}
		cout <<endl;
		int x;
		scanf("%d", &x);
		pref[i] = x;
		if (x == pref[i-1] + 1) continue;
		int l = 0;
		int jump = 256;
		for ( ; jump ; jump/=2) {
			int pos = l + jump;
			if (pos >= i) continue;
			if (check(pos, i)) {
				l = pos;
			}
		}
		merge(l, i);
	}
	int f = 1;
	printf("0 ");
	for (int i=0 ; i<n ; i++) {
		if (!M[find(i)]) {
			M[find(i)]=f;
			f++;
		}
		printf("%d ", M[find(i)]);
	}
	cout <<endl;
	return 0;
}

Compilation message

carnival.cpp: In function 'bool check(int, int)':
carnival.cpp:33:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &x);
  ~~~~~^~~~~~~~~~
carnival.cpp:39:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &y);
  ~~~~~^~~~~~~~~~
carnival.cpp: In function 'int main()':
carnival.cpp:46:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
carnival.cpp:58:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &x);
   ~~~~~^~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 376 KB Output is correct
2 Correct 21 ms 376 KB Output is correct
3 Correct 11 ms 376 KB Output is correct
4 Correct 6 ms 252 KB Output is correct
5 Correct 17 ms 376 KB Output is correct
6 Correct 9 ms 376 KB Output is correct
7 Correct 21 ms 248 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 248 KB Output is correct
2 Correct 24 ms 248 KB Output is correct
3 Correct 12 ms 376 KB Output is correct
4 Correct 6 ms 408 KB Output is correct
5 Correct 16 ms 248 KB Output is correct
6 Correct 15 ms 248 KB Output is correct
7 Correct 12 ms 248 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 376 KB Output is correct
2 Correct 22 ms 248 KB Output is correct
3 Correct 22 ms 312 KB Output is correct
4 Correct 6 ms 312 KB Output is correct
5 Correct 18 ms 248 KB Output is correct
6 Correct 14 ms 252 KB Output is correct
7 Correct 15 ms 320 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 376 KB Output is correct
2 Correct 22 ms 248 KB Output is correct
3 Correct 10 ms 248 KB Output is correct
4 Correct 6 ms 316 KB Output is correct
5 Correct 15 ms 376 KB Output is correct
6 Correct 12 ms 424 KB Output is correct
7 Correct 21 ms 376 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 376 KB Output is correct
2 Correct 20 ms 248 KB Output is correct
3 Correct 10 ms 316 KB Output is correct
4 Correct 15 ms 248 KB Output is correct
5 Correct 13 ms 248 KB Output is correct
6 Correct 9 ms 376 KB Output is correct
7 Correct 7 ms 248 KB Output is correct