Submission #1158503

#	Time	Username	Problem	Language	Result	Execution time	Memory
1158503		KawakiMeido	Swap (BOI16_swap)	C++20	0 / 100	5 ms	9792 KiB

swap

/*Author: KawakiMeido*/
#include <bits/stdc++.h>
#define pb push_back
#define endl "\n"
#define ll long long
#define all(x) (x).begin(),(x).end()
#define pii pair<int,int>
#define piii pair<int,pii>
#define fi first
#define se second

using namespace std;

/*Constants*/
const int N = 2e5+10;
const int INF = 1e9+7;
const long long LLINF = 1e18+3;

/*TestCases*/
int test=1;
void solve();
void TestCases(bool v){
    if (v) cin >> test;
    while(test--) solve();
}

/*Global Variables*/
int n;
int a[N], ans[N];
vector<piii> dp[N*2];

void DFS(int u){
    int val0 = INF, val1 = INF;

    if (u*2 <= n){
        DFS(u*2);
        val0 = a[u*2];
    }
    if (u*2+1<=n){
        DFS(u*2+1);
        val1 = a[u*2+1];
    }

    if (val0 == INF && val1 == INF){
        dp[u].push_back({n+1,{u,-1}});
        return;
    }
    if (val0 < val1){
        vector<piii>& dp0 = dp[u*2];
        int initval = val0;
        int idx0 = 0;
        while (idx0!=(int)dp0.size() && dp0[idx0].fi < initval) ++ idx0;

        dp[u].push_back({initval,{u,-1}});

        while (idx0!=(int)dp0.size()){
            dp[u].push_back({dp0[idx0].fi,{dp0[idx0].se.fi,0}});
            ++idx0;
        }
    }

    else{
        vector<piii>& dp0 = dp[u*2];
        vector<piii>& dp1 = dp[u*2+1];
        int midval = max(val0,val1);
        int initval = min(val0,val1);

        int idx0 = 0, idx1 = 0;
        bool changed = false;
        while (idx0!=(int)dp0.size() && dp0[idx0].fi < initval) ++ idx0;
        while (idx1!=(int)dp1.size() && dp1[idx1].fi < initval) ++ idx1;

        dp[u].push_back({initval,{u,-1}});

        while (!(idx0==(int)dp0.size() || idx1==(int)dp1.size())){
            int mnpos = min({dp0[idx0].fi,dp1[idx1].fi});
            if (!changed) mnpos = min(mnpos,midval);
            pii tmpval0 = {dp0[idx0].se.fi,0}, tmpval1 = {dp1[idx1].se.fi,1};
            pii mnval = (changed)? max(tmpval0,tmpval1): min(tmpval0,tmpval1);

            dp[u].push_back({mnpos,mnval});

            if (mnpos == midval){
                changed = true;
            }
            else if (mnpos == dp0[idx0].fi){
                ++idx0;
            }
            else{
                ++idx1;
            }
        }
    }
}

void Trace(int u, int val){
    piii tmp = {val,{INF,INF}};
    int pos = upper_bound(all(dp[u]),tmp) - dp[u].begin();

    if (dp[u][pos].se.se == -1){
        ans[u] = val;
        if (u*2 <= n) Trace(u*2,a[u*2]);
        if (u*2+1 <= n) Trace(u*2+1,a[u*2+1]);
    }
    else if (dp[u][pos].se.se == 0){
        ans[u] = min(a[u*2],a[u*2+1]);
        if (u*2 <= n) Trace(u*2,val);
        if (u*2+1 <= n) Trace(u*2+1,max(a[u*2],a[u*2+1]));
    }
    else{
        ans[u] = min(a[u*2],a[u*2+1]);
        if (u*2 <= n) Trace(u*2,max(a[u*2],a[u*2+1]));
        if (u*2+1 <= n) Trace(u*2+1,val);
    }
}

/*Solution*/
void solve(){
    cin >> n;
    for (int i=1; i<=n; i++){
        cin >> a[i];
    }

    DFS(1);
    Trace(1,a[1]);
    for (int i=1; i<=n; i++){
        cout << ans[i] << " ";
    }

}

/*Driver Code*/
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    TestCases(0);

    return 0;
}

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