Submission #721342

#	Time	Username	Problem	Language	Result	Execution time	Memory
721342		rainboy	medians (balkan11_medians)	C11	100 / 100	28 ms	4304 KiB

medians

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

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 / 65
• Subtask 2: 35 / 35