Submission #1000920

#	Time	Username	Problem	Language	Result	Execution time	Memory
1000920		irmuun	Building 4 (JOI20_building4)	C++17	0 / 100	0 ms	348 KiB

building4

#include<bits/stdc++.h>

using namespace std;

#define ll long long
#define pb push_back
#define ff first
#define ss second
#define all(s) s.begin(),s.end()
#define rall(s) s.rbegin(),s.rend()

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    ll n;
    cin>>n;
    ll a[2*n+5],b[2*n+5];
    for(ll i=1;i<=2*n;i++){
        cin>>a[i];
    }
    for(ll i=1;i<=2*n;i++){
        cin>>b[i];
    }
    pair<ll,ll>dp[2*n+5][2];
    ll bef[2*n+5][2];
    memset(bef,-1,sizeof bef);
    for(ll i=1;i<=2*n;i++){
        for(ll j=0;j<2;j++){
            dp[i][j]={-1,-1};
        }
    }
    dp[1][0]={1,1};
    dp[1][1]={0,0};
    for(ll i=2;i<=2*n;i++){
        if((dp[i-1][0].ff!=-1 && a[i-1]<=a[i])&&(dp[i-1][1].ff!=-1 && b[i-1]<=a[i])){
            pair<ll,ll>a=dp[i-1][0];
            pair<ll,ll>b=dp[i-1][1];
            ll l=min(a.ff,b.ff),r=max(a.ss,b.ss);
            dp[i][0]={l+1,r+1};
            bef[i][0]=0;
        }
        else if(dp[i-1][0].ff!=-1&&a[i-1]<=a[i]){
            dp[i][0]=dp[i-1][0];
            dp[i][0].ff++;
            dp[i][0].ss++;
            bef[i][0]=0;
        }
        else if(dp[i-1][1].ff!=-1&&b[i-1]<=a[i]){
            dp[i][0]=dp[i-1][1];
            dp[i][0].ff++;
            dp[i][0].ss++;
            bef[i][0]=1;
        }
        
        if((dp[i-1][0].ff!=-1&&a[i-1]<=b[i])&&(dp[i-1][1].ff!=-1&&b[i-1]<=b[i])){
            pair<ll,ll>a=dp[i-1][0];
            pair<ll,ll>b=dp[i-1][1];
            ll l=min(a.ff,b.ff),r=max(a.ss,b.ss);
            dp[i][1]={l,r};
            bef[i][1]=0;
        }
        else if(dp[i-1][0].ff!=-1&&a[i-1]<=b[i]){
            dp[i][1]=dp[i-1][0];
            bef[i][1]=0;
        }
        else if(dp[i-1][1].ff!=-1&&b[i-1]<=b[i]){
            dp[i][1]=dp[i-1][1];
            bef[i][1]=1;
        }
    }
    ll pos=-1;
    if(dp[2*n][0].ff<=n&&n<=dp[2*n][0].ss){
        pos=0;
    }
    if(dp[2*n][1].ff<=n&&n<=dp[2*n][1].ss){
        pos=1;
    }
    if(pos==-1){
        cout<<-1;
        return 0;
    }
    for(ll i=2*n;i>=1;i--){
        if(pos==0){
            cout<<'A';
        }
        else{
            cout<<'B';
        }
        pos=bef[i][pos];
    }
}

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