제출 #1253119

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1253119		nrg_studio	Swap (BOI16_swap)	C++20	100 / 100	812 ms	13128 KiB

swap

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pb push_back
#define pii pair<int,int>
#define f first
#define s second
#define chmin(a, b) a = min(a,b)
#define chmax(a, b) a = max(a,b)
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define F0R(i, a) for (int i = 0; i < (a); i++)
#define all(x) x.begin(),x.end()
#define vec vector

const int N = 2e5, l2 = 36;
bool dp[N][l2][2] = {false};
int a[N], sz[N];
int n;

vec<int> st;
vec<int> p1, p2;
queue<array<int,3>> q;

void get(vec<int>& p) {
    p.clear();
    while (q.size()) {
        array<int,3> cur = q.front(); q.pop();
        int l = 2*cur[0]+1, r = 2*cur[0]+2, i = cur[1];
        if (l<n) {
            if (dp[cur[0]][i][0]) {
                q.push({{l,cur[1],cur[2]}});
                cur[1] = sz[l]-1; cur[2] = a[l];
            } else {
                q.push({{l,sz[l]-1,a[l]}});
            }

            if (r<n) {
                if (dp[cur[0]][i][1]) {
                    q.push({{r,cur[1],cur[2]}});
                    cur[2] = a[r];
                } else {
                    q.push({{r,sz[r]-1,a[r]}});
                }
            }
        }
        p.pb(cur[2]);
    }
}

bool cmp() {
    for (int i=0;i<p1.size();i++) {
        if (p1[i]>p2[i]) {return false;}
        if (p1[i]<p2[i]) {return true;}
    } return true;
}

void dfs(int cur=0) {
    sz[cur] = st.size();
    if (2*cur+1<n) {
        st.pb(a[2*cur+1]);
        dfs(2*cur+1);

        if (2*cur+2<n) {
            st.pb(a[2*cur+2]);
            dfs(2*cur+2);
            st.pop_back();
        }
        st.pop_back();

        int l = a[2*cur+1], r = (2*cur+2>=n ? 3e5 : a[2*cur+2]);
        for (int i=0;i<st.size();i++) {
            //cout<<st[i]<<' ';
            int x = st[i];
            //if (x==3 && cur==1) {cout << x << ' ' << l << ' ' << r << '\n';}
            if (l<min(x,r)) {
                dp[cur][i][0] = true;
            } else if (r<min(x,l)) {
                dp[cur][i][0] = dp[cur][i][1] = true;
                q.push({{cur,i,x}});
                get(p1);

                dp[cur][i][0] = false;
                q.push({{cur,i,x}});
                get(p2);
                
                if (cmp()) {dp[cur][i][0] = true;}
            }
        }//cout<<'\n';
    }


}

int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    
    cin >> n;
    for (int i=0;i<n;i++) {cin >> a[i];}

    st.pb(a[0]);
    dfs();
    q.push({{0,0,a[0]}});
    get(p1);
    for (int i=0;i<n;i++) {cout << p1[i] << ' ';}

    //cout << dp[1][0][0]<<' '<<dp[1][0][1]<<'\n';
}

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