Submission #96427

#TimeUsernameProblemLanguageResultExecution timeMemory
96427ics0503Swap (BOI16_swap)C++17
68 / 100
527 ms14372 KiB
#include<stdio.h> #include<algorithm> using namespace std; int a[33][121212], n, ck[33][121212],A[33][121212], ADN[33]; void mkA(int dep, int w) { if (n < w)return; A[dep][ADN[dep]++] = w; ck[dep][w] = 0; a[dep][w] = a[dep - 1][w]; mkA(dep, w * 2); mkA(dep, w * 2 + 1); } void mkck(int dep, int w) { if (n < w)return; ck[dep][w] = 1; mkck(dep, w * 2); mkck(dep, w * 2 + 1); } void cpy(int dep, int w) { if (n < w)return; a[dep][w] = a[dep + 1][w]; cpy(dep, w * 2); cpy(dep, w * 2 + 1); } int go(int dep, int G, int w) { ADN[dep] = 0; mkA(dep, w); a[dep][w] = G; for (int x = 0; x < ADN[dep]; x++) { int now = A[dep][x]; if (ck[dep][now])continue; int l = now * 2, r = now * 2 + 1; if (l > n)continue; if (r > n){ if(a[dep][now] > a[dep][l]) swap(a[dep][now], a[dep][l]); continue; } if (a[dep][now] < a[dep][l] && a[dep][now] < a[dep][r])continue; else if (a[dep][l] < a[dep][r] && a[dep][l] < a[dep][now])swap(a[dep][now], a[dep][l]); else { int mn = min(a[dep][l], a[dep][now]); int mx = max(a[dep][l], a[dep][now]); a[dep][now] = a[dep][r]; mkck(dep, now); int L = go(dep + 1, mn, now * 2), R = go(dep + 1, mn, now * 2 + 1), p, q; if (L < R) p = now * 2, q = now * 2 + 1; else p = now * 2 + 1, q = now * 2; cpy(dep, p); go(dep + 1, mx, q); cpy(dep, q); } } for (int x = 0; x < ADN[dep]; x++)if (a[dep][A[dep][x]] == G)return A[dep][x]; } int main() { scanf("%d", &n); for (int i = 1; i <= n; i++)scanf("%d", &a[0][i]); go(1, a[0][1], 1); for (int i = 1; i <= n; i++) printf("%d ", a[1][i]); return 0; }

Compilation message (stderr)

swap.cpp: In function 'int go(int, int, int)':
swap.cpp:49:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^
swap.cpp: In function 'int main()':
swap.cpp:51:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
swap.cpp:52:35: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for (int i = 1; i <= n; i++)scanf("%d", &a[0][i]);
                              ~~~~~^~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...