제출 #1319124

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

building4

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

ii dp[maxn+2][2];
int a[maxn+2][2];

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

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

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

                    dp[q][ty].fir=min(dp[q][ty].fir,baru.fir);
                    dp[q][ty].sec=max(dp[q][ty].sec,baru.sec);
                }
            }
        }
    }

    // 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";
            }
            else{
                ans+="A";
                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;
                }
            }
        }
        reverse(ans.begin(),ans.end());
        cout<<ans<<endl;

    }


}

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