#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 return dp[u][vl]=min(getdp(2*u, vl), getdp(2*u+1, 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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |