Submission #154627

#	Time	Username	Problem	Language	Result	Execution time	Memory
154627		ivandasfs	Carnival (CEOI14_carnival)	C++14	100 / 100	24 ms	424 KiB

carnival

#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 (stderr)

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 / 20
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 20 / 20
• Subtask 5: 20 / 20