Submission #1000933

#	Time	Username	Problem	Language	Result	Execution time	Memory
1000933		irmuun	Building 4 (JOI20_building4)	C++17	100 / 100	243 ms	84556 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]=2;
        }
        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]=2;
        }
        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;
    }
    ll cur=n;
    string s="";
    for(ll i=2*n;i>=1;i--){
        if(pos==0){
            s+='A';
            cur--;
        }
        else{
            s+='B';
        }
        if(bef[i][pos]<2){
            pos=bef[i][pos];
        }
        else{
            if(dp[i-1][0].ff<=cur&&cur<=dp[i-1][0].ss){
                pos=0;
            }
            else{
                pos=1;
            }
        }
    }
    reverse(all(s));
    cout<<s;
}

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