Submission #480127

#	Time	Username	Problem	Language	Result	Execution time	Memory
480127		rainboy	Slagalica (COCI19_slagalica2)	C11	70 / 70	52 ms	1740 KiB

slagalica

#include <stdio.h>
 
#define T	4
#define N	100000
 
unsigned int X = 12345;
 
int rand_() {
	return (X *= 3) >> 1;
}
 
void sort(int *aa, int l, int r) {
	while (l < r) {
		int i = l, j = l, k = r, a = aa[l + rand_() % (r - l)], tmp;
 
		while (j < k)
			if (aa[j] == a)
				j++;
			else if (aa[j] > a) {
				tmp = aa[i], aa[i] = aa[j], aa[j] = tmp;
				i++, j++;
			} else {
				k--;
				tmp = aa[j], aa[j] = aa[k], aa[k] = tmp;
			}
		sort(aa, l, i);
		l = k;
	}
}
 
int aa[T][N], kk[N];
 
int ok(int *kk, int u, int v) {
	if (kk[0] + kk[3] == 0)
		return u == v && (u == 0 ? kk[2] == 0 : kk[1] == 0);
	else if (u == 0 && v == 1)
		return kk[0] == kk[3] + 1;
	else if (u == 1 && v == 0)
		return kk[3] == kk[0] + 1;
	else
		return kk[0] == kk[3];
}
 
int main() {
	int n, i, t, u, v, a_, b_;
 
	scanf("%d", &n);
	u = v = -1, a_ = b_ = -1;
	for (i = 0; i < n; i++) {
		int a;
 
		scanf("%d%d", &t, &a);
		if (t == 5)
			u = 1, a_ = a;
		else if (t == 6)
			u = 0, a_ = a;
		else if (t == 7)
			v = 0, b_ = a;
		else if (t == 8)
			v = 1, b_ = a;
		else
			t--, aa[t][kk[t]++] = a;
	}
	if (!ok(kk, u, v)) {
		printf("-1\n");
		return 0;
	}
	for (t = 0; t < T; t++)
		sort(aa[t], 0, kk[t]);
	printf("%d", a_);
	for (i = 0; i < n - 2; i++) {
		int t_;
 
		t_ = -1;
		for (t = 0; t < T; t++)
			if (kk[t] > 0 && u == t / 2) {
				kk[t]--;
				if (ok(kk, t % 2 ^ 1, v) && (t_ == -1 || aa[t_][kk[t_] - 1] > aa[t][kk[t]]))
					t_ = t;
				kk[t]++;
			}
		t = t_;
		printf(" %d", aa[t][--kk[t]]), u = t % 2 ^ 1;
	}
	printf(" %d\n", b_);
	return 0;
}

Compilation message (stderr)

slagalica.c: In function 'main':
slagalica.c:47:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   47 |  scanf("%d", &n);
      |  ^~~~~~~~~~~~~~~
slagalica.c:52:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   52 |   scanf("%d%d", &t, &a);
      |   ^~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 5 / 5
• Subtask 4: 5 / 5
• Subtask 5: 5 / 5
• Subtask 6: 5 / 5
• Subtask 7: 5 / 5
• Subtask 8: 5 / 5
• Subtask 9: 5 / 5
• Subtask 10: 5 / 5
• Subtask 11: 5 / 5
• Subtask 12: 5 / 5
• Subtask 13: 5 / 5
• Subtask 14: 5 / 5