Submission #229670

#TimeUsernameProblemLanguageResultExecution timeMemory
229670DrSwadSwap (BOI16_swap)C++17
100 / 100
101 ms7544 KiB
#include <bits/stdc++.h> using namespace std; #ifdef LOCAL #include "/Users/swad/Desktop/CP/debug.h" #endif const int N = int(2e5) + 10; int n; int a[N << 1]; int at[N << 1]; int to[N << 1]; int vis[N << 1]; void setVis(int at, int val) { if (vis[at]) return; vis[at] = val; while (at) { if (vis[at << 1] == 1) to[at] = to[at << 1]; else if (vis[at << 1 | 1] != 1) to[at] = at; else if (vis[at << 1] == -1) to[at] = to[at << 1 | 1]; else to[at] = min(to[at << 1], to[at << 1 | 1]); at >>= 1; } } void cancelVis(int from) { int at = from; while (at < to[from]) { if (vis[at << 1] == 1) at <<= 1; else if (vis[at << 1] == -1) (at <<= 1) |= 1; else { if (to[at << 1] < to[at << 1 | 1]) setVis(at << 1, 1), at <<= 1; else setVis(at << 1, -1), (at <<= 1) |= 1; } } if (vis[at << 1] != -1) setVis(at << 1, -1); if (vis[at << 1 | 1] != -1) setVis(at << 1 | 1, -1); } int main() { #ifdef LOCAL freopen("in", "r", stdin); freopen("out", "w", stdout); #endif scanf("%d", &n); for (int i = 1; i <= n; i++) { scanf("%d", &a[i]); at[a[i]] = i; } iota(to, to + (N << 1), 0); memset(&vis[n + 1], -1, sizeof(int) * ((N << 1) - (n + 1))); setVis(1, -1); for (int i = 1; i <= n; i++) { if (vis[at[i]] != -1) { if (at[i] & 1) setVis(at[i], 1); else { if (vis[at[i] + 1] != 1) setVis(at[i], 1), setVis(at[i] + 1, -1); else if (vis[at[i]] == 1) cancelVis(at[i] + 1); else { if (to[at[i]] < to[at[i] + 1]) { cancelVis(at[i]); setVis(at[i], -1); } else { cancelVis(at[i] + 1); setVis(at[i], 1); } } } } else cancelVis(at[i]); } for (int i = 2; i <= n; i++) if (vis[i] == 1) swap(a[i], a[i >> 1]); for (int i = 1; i <= n; i++) { if (i > 1) printf(" "); printf("%d", a[i]); } puts(""); return 0; }

Compilation message (stderr)

swap.cpp: In function 'int main()':
swap.cpp:50:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
swap.cpp:52:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &a[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...