oj.uz

Submission #480127

# Submission time Handle Problem Language Result Execution time Memory
480127 2021-10-14T18:52:02 Z rainboy Slagalica (COCI19_slagalica2) C
70 / 70
 52 ms 1740 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 1392 KB Output is correct
2 Correct 26 ms 544 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 1380 KB Output is correct
2 Correct 16 ms 588 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 636 KB Output is correct
2 Correct 50 ms 1488 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 608 KB Output is correct
2 Correct 51 ms 1288 KB Output is correct
3 Correct 41 ms 1540 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 1448 KB Output is correct
2 Correct 17 ms 536 KB Output is correct

Subtask #8
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 1360 KB Output is correct
2 Correct 20 ms 636 KB Output is correct
3 Correct 42 ms 1476 KB Output is correct

Subtask #9
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 572 KB Output is correct
2 Correct 39 ms 1428 KB Output is correct

Subtask #10
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 1632 KB Output is correct
2 Correct 18 ms 1528 KB Output is correct

Subtask #11
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 1348 KB Output is correct
2 Correct 17 ms 1624 KB Output is correct

Subtask #12
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 1604 KB Output is correct
2 Correct 18 ms 1740 KB Output is correct

Subtask #13
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 1376 KB Output is correct
2 Correct 18 ms 1536 KB Output is correct

Subtask #14
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 1348 KB Output is correct
2 Correct 19 ms 1612 KB Output is correct