Submission #1173945

#TimeUsernameProblemLanguageResultExecution timeMemory
117394512345678Swap (BOI16_swap)C++20
48 / 100
12 ms12104 KiB
#include <bits/stdc++.h> using namespace std; const int nx=2e5+5; int n, a[nx], lvl[nx]; map<int, int> dp[nx]; int getdp(int u, int vl) { if (dp[u].find(vl)!=dp[u].end()) return dp[u][vl]; if (2*u>n) return dp[u][vl]=lvl[u]; if (2*u==n) { if (a[u]<a[2*u]) return dp[u][vl]=lvl[u]; else return dp[u][vl]=lvl[u]+1; } int mn=min({vl, a[2*u], a[2*u+1]}); if (vl==mn) return dp[u][vl]=lvl[u]; else if (a[2*u]==mn) return dp[u][vl]=getdp(2*u, vl); else { if (vl<a[2*u]) { if (getdp(2*u, vl)<=getdp(2*u+1, vl)) return dp[u][vl]=getdp(2*u, vl); else return dp[u][vl]=getdp(2*u+1, vl); } else { if (getdp(2*u, a[2*u])<=getdp(2*u+1, a[2*u])) return dp[u][vl]=getdp(2*u+1, vl); else return dp[u][vl]=getdp(2*u, vl); } } } void solve(int u) { if (2*u>n) return; if (2*u==n) { if (a[2*u]<a[u]) swap(a[u], a[2*u]); return; } int mn=min({a[u], a[2*u], a[2*u+1]}); if (a[u]==mn) solve(2*u), solve(2*u+1); else if (a[2*u]==mn) swap(a[u], a[2*u]), solve(2*u), solve(2*u+1); else { if (a[2*u]<a[u]) swap(a[u], a[2*u]); if (getdp(2*u, a[u])<=getdp(2*u+1, a[u])) swap(a[u], a[2*u]), swap(a[u], a[2*u+1]), solve(2*u), solve(2*u+1); else swap(a[u], a[2*u+1]), solve(2*u), solve(2*u+1); } } int main() { cin.tie(NULL)->sync_with_stdio(false); cin>>n; for (int i=1; i<=n; i++) cin>>a[i], lvl[i]=lvl[i/2]+1; solve(1); for (int i=1; i<=n; i++) cout<<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...