제출 #1319103

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1319103		wangzhiyi33	건물 4 (JOI20_building4)	C++20	11 / 100	2092 ms	46540 KiB

building4

#include <bits/stdc++.h>
using namespace std;
#define int long long
#pragma GCC optimize("O3,unroll-loops")
#define ii pair<int,int>
#define fir first
#define sec second
#define pb push_back
const int maxn=5e5;

ii merg(ii a,ii b){
    ii ans={min(a.fir,b.fir),max(a.sec,b.sec)};
    return ans;
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int n; cin>>n;
    int a[2*n+2][2];
    a[2*n+1][0]=a[2*n+1][1]=1e18;
    a[0][0]=a[0][1]=-1e18;

    for(int q=1;q<=2*n;q++){
        cin>>a[q][0];
    }
    for(int q=1;q<=2*n;q++){
        cin>>a[q][1];
    }
    ii dp[2*n+2][2];
    dp[0][0]={0,0};
    dp[0][1]={0,0};

    for(int q=1;q<=2*n;q++){
        dp[q][0]=dp[q][1]={2*n,-2*n};
        for(int ty=0;ty<2;ty++){
            for(int prv=0;prv<2;prv++){
                if(a[q-1][prv]<=a[q][ty]){
                    if(dp[q-1][prv].sec<=-1)continue;
                    ii baru=dp[q-1][prv];
                    if(ty==0)baru.fir++,baru.sec++;

                    dp[q][ty]=merg(dp[q][ty],baru);
                }
            }
        }
    }

    // for(int q=1;q<=2*n;q++){
    //     cout<<dp[q][0].fir<<" "<<dp[q][0].sec<<" "<<dp[q][1].fir<<" "<<dp[q][1].sec<<endl;
    // }

    int ty=-1;
    for(int q=0;q<2;q++){
        if(dp[2*n][q].sec<0)continue;
        if(dp[2*n][q].fir<=n && dp[2*n][q].sec>=n){
            ty=q;
        }
    }

    if(ty==-1){
        cout<<-1<<endl;
    }
    else{
        string ans;
        int cnt=n;
        for(int q=2*n;q>=1;q--){
            if(ty){
                ans="B"+ans;
            }
            else{
                ans="A"+ans;
                cnt--;
            }
            for(int prv=0;prv<=1;prv++){
                if(dp[q-1][prv].sec<0)continue;
                if(dp[q-1][prv].fir<=cnt && cnt<=dp[q-1][prv].sec && a[q-1][prv]<=a[q][ty]){
                    ty=prv;break;
                }
            }
        }
        cout<<ans<<endl;

    }


}

• Subtask 1: 11 / 11
• Subtask 2: 0 / 89