#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; }

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));
      |          ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~