Submission #544729

#	Time	Username	Problem	Language	Result	Execution time	Memory
544729		rainboy	Swap (BOI16_swap)	C11	100 / 100	56 ms	4000 KiB

swap

#include <stdio.h>
#include <string.h>

#define N	200000

int ancestor(int i, int j) {
	return i == j || i < j && ancestor(i, j / 2);
}

int main() {
	static int aa[1 + N];
	static char swap[1 + N * 2];
	int n, i, j;

	scanf("%d", &n);
	for (i = 1; i <= n; i++)
		scanf("%d", &aa[i]);
	memset(swap, -1, n * sizeof *swap);
	for (j = 1; j <= n; j++) {
		int j_;

		i = j * 2 > n ? -1 : (j * 2 < n && aa[j * 2 + 1] < aa[j * 2] ? j * 2 + 1 : j * 2);
		for (j_ = j; j_ >= 1; j_ /= 2)
			if ((j_ & 1) == 0) {
				if (swap[j_] != 1 && (i == -1 || aa[i] > aa[j_]))
					i = j_;
				if (swap[j_] == 0)
					break;
			} else {
				if (swap[j_] != 1 && (i == -1 || aa[i] > aa[j_]))
					i = j_;
				if (j_ > 1 && swap[j_ ^ 1] != 0 && swap[j_] != 0 && (i == -1 || aa[i] > aa[j_ ^ 1]))
					i = j_ ^ 1;
				if (j_ == 1 || swap[j_ ^ 1] == 1 || swap[j_] == 0)
					break;
			}
		if (i == j * 2)
			swap[j * 2] = 1, swap[j * 2 + 1] = 0;
		else if (i == j * 2 + 1)
			swap[j * 2 + 1] = 1;
		else {
			swap[j * 2] = swap[j * 2 + 1] = 0;
			if (ancestor(i, j))
				swap[i] = 0;
			else
				swap[i ^ 1] = swap[i] = 1, i ^= 1;
			for (j_ = j; j_ != i; j_ /= 2) {
				if ((j_ & 1) == 1)
					swap[j_ ^ 1] = 0;
				swap[j_] = 1;
			}
		}
	}
	for (i = 2; i <= n; i++) {
		int tmp;

		if (swap[i])
			tmp = aa[i], aa[i] = aa[i / 2], aa[i / 2] = tmp;
	}
	for (i = 1; i <= n; i++)
		printf("%d ", aa[i]);
	printf("\n");
	return 0;
}

Compilation message (stderr)

swap.c: In function 'ancestor':
swap.c:7:25: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
    7 |  return i == j || i < j && ancestor(i, j / 2);
      |                   ~~~~~~^~~~~~~~~~~~~~~~~~~~~
swap.c: In function 'main':
swap.c:15:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |  scanf("%d", &n);
      |  ^~~~~~~~~~~~~~~
swap.c:17:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |   scanf("%d", &aa[i]);
      |   ^~~~~~~~~~~~~~~~~~~
In file included from /usr/include/string.h:495,
                 from swap.c:2:
In function 'memset',
    inlined from 'main' at swap.c:18:2:
/usr/include/x86_64-linux-gnu/bits/string_fortified.h:71:10: warning: '__builtin___memset_chk' specified size between 18446744071562067968 and 18446744073709551615 exceeds maximum object size 9223372036854775807 [-Wstringop-overflow=]
   71 |   return __builtin___memset_chk (__dest, __ch, __len, __bos0 (__dest));
      |          ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 11 / 11
• Subtask 3: 27 / 27
• Subtask 4: 20 / 20
• Subtask 5: 32 / 32