Submission #573185

#	Time	Username	Problem	Language	Result	Execution time	Memory
573185		fdnfksd	Swap (BOI16_swap)	C++17	0 / 100	10 ms	14424 KiB

swap

#include<bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma,popcnt")
#define pli pair<long long,long long>
#define pb push_back
const long long INF=-1e18;
using namespace std;
using ll =long long ;
const ll maxN=3e5+1;
ll n, a[maxN];
map<int,int>pos[maxN];
ll final_pos(ll i, ll val)
{
    if(i*2>n) return pos[i][val]=i;
    if(pos[i][val]>0) return pos[i][val];
    ll mn=min(a[i*2],a[i*2+1]);
    if(mn>=val) return pos[i][val]=val;
    else
    {
        if(mn==a[i*2])
        {
            return pos[i][val]=final_pos(i*2,val);
        }
        else
        {
            ll mx_child=max(val,a[i*2]);
            ll mn_child=min(val,a[i*2]);
            ll left=final_pos(i*2,mn_child);
            ll right=final_pos(i*2+1,mn_child);
            if(left<=right)
            {
                // con trai nhan gia tri min
                if(mn_child==val) pos[i][val]=final_pos(i*2,val);
                else pos[i][val]=final_pos(i*2+1,val);
            }
            else
            {
                if(mn_child==val) pos[i][val]=final_pos(i*2+1,val);
                else pos[i][val]=final_pos(i*2,val);
            }
        }
    }
    return pos[i][val];
}
void solve()
{
    cin >> n;
    for(int i=1;i<=n;i++) cin >> a[i];
    a[n+1]=1e10;
    for(int i=1;i<=n;i++)
    {
        if(i*2>n) continue;
        ll mn=min(a[i*2],a[i*2+1]);
        if(mn>=a[i]) continue;
        else
        {
            if(mn==a[i*2]) swap(a[i],a[i*2]);
            else
            {
                swap(a[i],a[i*2+1]);
                ll mn_child=min(a[i*2+1],a[i*2]);
                ll mx_child=max(a[i*2+1],a[i*2]);
                ll left=final_pos(i*2,mn_child);
                ll right=final_pos(i*2+1,mn_child);
                if(left<=right)
                {
                    a[i*2]=mn_child;
                    a[i*2+1]=mx_child;
                }
                else
                {
                    a[i*2]=mx_child;
                    a[i*2+1]=mn_child;
                }
            }
        }
    }
    for(int i=1;i<=n;i++) cout << a[i]<<' ';
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	solve();
}

Compilation message (stderr)

swap.cpp: In function 'll final_pos(ll, ll)':
swap.cpp:27:16: warning: unused variable 'mx_child' [-Wunused-variable]
   27 |             ll mx_child=max(val,a[i*2]);
      |                ^~~~~~~~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 11
• Subtask 3: 0 / 27
• Subtask 4: 0 / 20
• Subtask 5: 0 / 32