oj.uz

Submission #1071663

# Submission time Handle Problem Language Result Execution time Memory
1071663 2024-08-23T09:47:20 Z rainboy Pizza Party (CCO24_day1problem2) C
12 / 12
 612 ms 51024 KB 
#include <stdio.h>

#define N	1000000

int max(int a, int b) { return a > b ? a : b; }

unsigned int Z = 12345;

int rand_() {
	return (Z *= 3) >> 1;
}

int *xx;

void sort(int *ii, int l, int r) {
	while (l < r) {
		int i = l, j = l, k = r, i_ = ii[l + rand_() % (r - l)], tmp;

		while (j < k) {
			int c = xx[ii[j]] != xx[i_] ? xx[ii[j]] - xx[i_] : ii[j] - i_;

			if (c == 0)
				j++;
			else if (c < 0) {
				tmp = ii[i], ii[i] = ii[j], ii[j] = tmp;
				i++, j++;
			} else {
				k--;
				tmp = ii[j], ii[j] = ii[k], ii[k] = tmp;
			}
		}
		sort(ii, l, i);
		l = k;
	}
}

int ft[N];

void update(int i, int n, int x) {
	while (i < n) {
		ft[i] = max(ft[i], x);
		i |= i + 1;
	}
}

int query(int i) {
	int x = 0;

	while (i >= 0) {
		x = max(x, ft[i]);
		i &= i + 1, i--;
	}
	return x;
}

int main() {
	static int aa[N], bb[N], ii[N], jj[N], jj_[N];
	int n, h, i, j;

	scanf("%d", &n);
	for (i = 0; i < n; i++)
		scanf("%d", &aa[n - 1 - i]);
	for (j = 0; j < n; j++)
		scanf("%d", &bb[j]);
	for (i = 0; i < n; i++)
		ii[i] = i;
	xx = aa, sort(ii, 0, n);
	for (j = 0; j < n; j++)
		jj[j] = j;
	xx = bb, sort(jj, 0, n);
	for (h = 0; h < n; h++) {
		if (aa[ii[h]] != bb[jj[h]]) {
			printf("-1\n");
			return 0;
		}
		jj_[ii[h]] = jj[h];
	}
	for (i = n - 1; i >= 0; i--) {
		j = jj_[i];
		update(j, n, aa[i] = bb[j] = query(j) + 1);
	}
	printf("%d\n", query(n - 1));
	for (i = n - 1; i >= 0; i--)
		printf("%d%c", aa[i], i > 0 ? ' ' : '\n');
	for (j = 0; j < n; j++)
		printf("%d%c", bb[j], j + 1 < n ? ' ' : '\n');
	return 0;
}

Compilation message

Main.c: In function 'main':
Main.c:60:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   60 |  scanf("%d", &n);
      |  ^~~~~~~~~~~~~~~
Main.c:62:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   62 |   scanf("%d", &aa[n - 1 - i]);
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.c:64:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   64 |   scanf("%d", &bb[j]);
      |   ^~~~~~~~~~~~~~~~~~~

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 420 ms 27832 KB good job!
2 Correct 438 ms 31568 KB good job!
3 Correct 432 ms 31780 KB good job!
4 Correct 428 ms 31568 KB good job!
5 Correct 432 ms 31568 KB good job!
6 Correct 429 ms 31772 KB good job!
7 Correct 438 ms 31724 KB good job!
8 Correct 423 ms 31692 KB good job!
9 Correct 440 ms 31652 KB good job!
10 Correct 444 ms 31640 KB good job!
11 Correct 426 ms 31572 KB good job!
12 Correct 461 ms 31756 KB good job!
13 Correct 1 ms 10588 KB good job!
14 Correct 1 ms 10588 KB good job!
15 Correct 1 ms 10588 KB good job!
16 Correct 304 ms 24364 KB good job!
17 Correct 294 ms 24392 KB good job!
18 Correct 308 ms 24600 KB good job!
19 Correct 284 ms 24480 KB good job!
20 Correct 291 ms 24404 KB good job!
21 Correct 294 ms 24400 KB good job!
22 Correct 412 ms 31656 KB good job!
23 Correct 1 ms 10584 KB good job!

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 10588 KB good job!
2 Correct 4 ms 10588 KB good job!
3 Correct 3 ms 10588 KB good job!
4 Correct 2 ms 10588 KB good job!
5 Correct 3 ms 10760 KB good job!
6 Correct 3 ms 10588 KB good job!
7 Correct 3 ms 10584 KB good job!
8 Correct 5 ms 10584 KB good job!
9 Correct 4 ms 10584 KB good job!
10 Correct 5 ms 10588 KB good job!
11 Correct 3 ms 10896 KB good job!
12 Correct 3 ms 10712 KB good job!
13 Correct 5 ms 10588 KB good job!
14 Correct 3 ms 10584 KB good job!
15 Correct 3 ms 10720 KB good job!

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 610 ms 32468 KB good job!
2 Correct 454 ms 34132 KB good job!
3 Correct 612 ms 45928 KB good job!
4 Correct 466 ms 33976 KB good job!
5 Correct 589 ms 46100 KB good job!
6 Correct 412 ms 34080 KB good job!
7 Correct 459 ms 34156 KB good job!
8 Correct 592 ms 45980 KB good job!
9 Correct 590 ms 46124 KB good job!
10 Correct 593 ms 45908 KB good job!
11 Correct 569 ms 51024 KB good job!
12 Correct 565 ms 41296 KB good job!
13 Correct 574 ms 50976 KB good job!
14 Correct 560 ms 41300 KB good job!
15 Correct 414 ms 34128 KB good job!
16 Correct 416 ms 34132 KB good job!