제출 #1368633

#제출 시각아이디문제언어결과실행 시간메모리
1368633namious건물 4 (JOI20_building4)C++20
0 / 100
0 ms344 KiB
#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define lc (id*2)
#define rc (id*2+1)
#define mid (r+l)/2
#define pb push_back
#define ll long long
#define int long long
#define pii pair<int,int>
#pragma GCC optimize("O3,unroll-loops")
#define fast_io ios_base::sync_with_stdio(0) ,cin.tie(0),cout.tie(0);

const int maxn = 1e6+6 , mod = 1e9+7 , inf = 1e15;

char ans[maxn];
int n,x,cur,a[maxn],b[maxn];
int dp[maxn][3][3];
pair<pii,char> nxt[maxn][3][3];

int32_t main(){
    fast_io

    cin >> n;
    for(int i = 1 ; i <= 2*n ; i++) cin >> a[i];
    for(int i = 1 ; i <= 2*n ; i++) cin >> b[i];

    for(int i = 1 ; i <= 2*n ; i++){
        for(int j = 1 ; j <= 2 ; j++){
            for(int k = 1 ; k <= 2 ; k++){
                dp[i][j][k] = inf;
            }
        }
    }

    dp[1][1][1] = 1; 
    nxt[1][1][1] = {{0,0},'A'};
    nxt[1][2][2] = {{0,0},'B'};

    for(int i = 1 ; i <= 2*n-1 ; i++){
        if(dp[i][1][1] == 0){
            if(a[i+1] >= a[i]){
                if(1ll < dp[i+1][1][1]){
                    nxt[i+1][1][1] = {{1,1},'A'};
                    dp[i+1][1][1] = min(dp[i+1][1][1],1ll);
                }
            }
            if(b[i+1] >= a[i]){
                if(1ll < dp[i+1][2][2]){
                    nxt[i+1][2][2] = {{1,1},'B'};
                    dp[i+1][2][2] = min(dp[i+1][2][2],1ll);
                }
            }
        }
        if(dp[i][1][1] >= 1){
            if(a[i+1] >= a[i]){
                if(dp[i][1][1]+1 < dp[i+1][1][1]){
                    nxt[i+1][1][1] = {{1,1},'A'};
                    dp[i+1][1][1] = min(dp[i+1][1][1],dp[i][1][1]+1);
                }
            }
            if(b[i+1] >= a[i]){
                if(dp[i][1][1]-1 < dp[i+1][2][1]){
                    nxt[i+1][2][1] = {{1,1},'B'};
                    dp[i+1][2][1] = min(dp[i+1][2][1],dp[i][1][1]-1);
                }
            }
        }
        if(dp[i][1][2] == 0){
            if(a[i+1] >= a[i]){
                if(1ll < dp[i+1][1][1]){
                    nxt[i+1][1][1] = {{1,2},'A'};
                    dp[i+1][1][1] = min(dp[i+1][1][1],1ll);
                }
            }
            if(b[i+1] >= a[i]){
                if(1ll < dp[i+1][2][2]){
                    nxt[i+1][2][2] = {{1,2},'B'};
                    dp[i+1][2][2] = min(dp[i+1][2][2],1ll);
                }
            }
        }
        if(dp[i][1][2] >= 1){
            if(a[i+1] >= a[i]){
                if(dp[i][1][2]-1 < dp[i+1][1][2]){
                    nxt[i+1][1][2] = {{1,2},'A'};
                    dp[i+1][1][2] = min(dp[i+1][1][2],dp[i][1][2]-1);
                }
            }
            if(b[i+1] >= a[i]){
                if(dp[i][1][2]+1 < dp[i+1][2][2]){
                    nxt[i+1][2][2] = {{1,2},'B'};
                    dp[i+1][2][2] = min(dp[i+1][2][2],dp[i][1][2]+1);
                }
            }
            // cout << "xxx" << " " << dp[i+1][1][2] << endl;
        }

        if(dp[i][2][1] == 0){
            if(a[i+1] >= b[i]){
                if(1ll < dp[i+1][1][1]){
                    nxt[i+1][1][1] = {{2,1},'A'};
                    dp[i+1][1][1] = min(dp[i+1][1][1],1ll);
                }
            }
            if(b[i+1] >= b[i]){
                if(1ll < dp[i+1][2][2]){
                    nxt[i+1][2][2] = {{2,1},'B'};
                    dp[i+1][2][2] = min(dp[i+1][2][2],1ll);
                }
            }
        }
        if(dp[i][2][1] >= 1){
            if(a[i+1] >= b[i]){
                if(dp[i][2][1]+1 < dp[i+1][1][1]){
                    nxt[i+1][1][1] = {{2,1},'A'};
                    dp[i+1][1][1] = min(dp[i+1][1][1],dp[i][2][1]+1);
                }
            }
            if(b[i+1] >= b[i]){
                if(dp[i][2][1]-1 < dp[i+1][2][1]){
                    nxt[i+1][2][1] = {{2,1},'B'};
                    dp[i+1][2][1] = min(dp[i+1][2][1],dp[i][2][1]-1);
                }
            }
        }
        if(dp[i][2][2] == 0){
            if(a[i+1] >= b[i]){
                if(1ll < dp[i+1][1][1]){
                    nxt[i+1][1][1] = {{2,2},'A'};
                    dp[i+1][1][1] = min(dp[i+1][1][1],1ll);
                }
            }
            if(b[i+1] >= b[i]){
                if(1ll < dp[i+1][2][2]){
                    nxt[i+1][2][2] = {{2,2},'B'};
                    dp[i+1][2][2] = min(dp[i+1][2][2],1ll);
                }
            }
        }
        if(dp[i][2][2] >= 1){
            if(a[i+1] >= b[i]){
                if(dp[i][2][2]-1 < dp[i+1][1][2]){
                    nxt[i+1][1][2] = {{2,2},'A'};
                    dp[i+1][1][2] = min(dp[i+1][1][2],dp[i][2][2]-1);
                }
            }
            if(b[i+1] >= b[i]){
                if(dp[i][2][2]+1 < dp[i+1][2][2]){
                    nxt[i+1][2][2] = {{2,2},'B'};
                    dp[i+1][2][2] = min(dp[i+1][2][2],dp[i][2][2]+1);
                }
            }
            // cout << "yyy" << " " << dp[i+1][1][2] << endl;
        }

        // if(dp[i+1][1][1] == 0) dp[i+1][1][2] = 0;
        // if(dp[i+1][1][2] == 0) dp[i+1][1][1] = 0;
        // if(dp[i+1][2][1] == 0) dp[i+1][2][2] = 0;
        // if(dp[i+1][2][2] == 0) dp[i+1][2][1] = 0;

        // for(int j = 1 ; j <= 2 ; j++){
        //     for(int k = 1 ; k <= 2 ; k++){
        //         cout << i+1 << " " << j << " " << k << " --- " << dp[i+1][j][k] << endl;
        //     }
        // }
    }

    int x = min({dp[2*n][1][1],dp[2*n][1][2],dp[2*n][2][1],dp[2*n][2][2]});
    if(x != 0) cout << -1;
    else{
        int i,j;
        if(dp[2*n][1][1] == 0) i = 1 , j = 1;
        if(dp[2*n][1][2] == 0) i = 1 , j = 2;
        if(dp[2*n][2][1] == 0) i = 2 , j = 1;
        if(dp[2*n][2][2] == 0) i = 2 , j = 2;
        vector <char> vec;
        int cur = 2*n;

        while(i != 0 or j != 0){
            int new_i = nxt[cur][i][j].first.first;
            int new_j = nxt[cur][i][j].first.second;
            vec.pb(nxt[cur][i][j].second);
            cur -- , i = new_i , j = new_j;
        }
        reverse(vec.begin(),vec.end());
        for(auto u : vec) cout << u;
    }

    return 0;
}
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…