oj.uz

Submission #721342

# Submission time Handle Problem Language Result Execution time Memory
721342 2023-04-10T17:58:47 Z rainboy medians (balkan11_medians) C
100 / 100
 28 ms 4304 KB 
#include <stdio.h>

#define N	100000

int main() {
	static int aa[N], bb[N * 2 - 1], kk[N * 2 - 1], qu1[N * 2 - 1], qu2[N * 2 - 1];
	int n, cnt1, cnt2, i, a;

	scanf("%d", &n);
	for (i = 0; i < n; i++) {
		scanf("%d", &aa[i]), aa[i]--;
		kk[aa[i]]++;
	}
	cnt1 = cnt2 = 0;
	for (a = 0; a < n - 1; a++)
		if (kk[a] == 0)
			qu1[cnt1++] = a;
	for (a = n * 2 - 2; a >= n; a--)
		if (kk[a] == 0)
			qu2[cnt2++] = a;
	for (i = n - 1; i > 0; i--)
		if (aa[i] > aa[i - 1]) {
			if (--kk[aa[i]] == 0)
				qu2[cnt2++] = aa[i];
			bb[i * 2 - 1] = qu2[--cnt2], bb[i * 2] = qu2[--cnt2];
		} else if (aa[i] < aa[i - 1]) {
			if (--kk[aa[i]] == 0)
				qu1[cnt1++] = aa[i];
			bb[i * 2 - 1] = qu1[--cnt1], bb[i * 2] = qu1[--cnt1];
		} else {
			kk[aa[i]]--;
			bb[i * 2 - 1] = qu1[--cnt1], bb[i * 2] = qu2[--cnt2];
		}
	bb[0] = aa[0];
	for (i = 0; i < n * 2 - 1; i++)
		printf("%d ", bb[i] + 1);
	printf("\n");
	return 0;
}

Compilation message

medians.c: In function 'main':
medians.c:9:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
    9 |  scanf("%d", &n);
      |  ^~~~~~~~~~~~~~~
medians.c:11:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   11 |   scanf("%d", &aa[i]), aa[i]--;
      |   ^~~~~~~~~~~~~~~~~~~

Subtask #1
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 296 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 288 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 292 KB Output is correct
7 Correct 1 ms 288 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 0 ms 292 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 340 KB Output is correct

Subtask #2
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 296 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 4 ms 596 KB Output is correct
4 Correct 5 ms 944 KB Output is correct
5 Correct 9 ms 1576 KB Output is correct
6 Correct 18 ms 2944 KB Output is correct
7 Correct 28 ms 4304 KB Output is correct