#include <bits/stdc++.h>
using namespace std;
const int nx=2e5+5;
int n, a[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]=u;
if (2*u==n)
{
if (vl<a[2*u]) return dp[u][vl]=u;
else return dp[u][vl]=2*u;
}
int mn=min({vl, a[2*u], a[2*u+1]});
if (vl==mn) return dp[u][vl]=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];
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... |