Submission #547707

#	Time	Username	Problem	Language	Result	Execution time	Memory
547707		krit3379	Building 4 (JOI20_building4)	C++17	100 / 100	875 ms	53204 KiB

building4

#include<bits/stdc++.h>
using namespace std;
#define N 1000005

int a[N],b[N],ar[2][N];
pair<int,int> dp[2][N];

int main(){
    int n,i,mi,ma,pos,now;
    string ans;
    cin>>n;
    for(i=1;i<=n<<1;i++)cin>>a[i],dp[0][i]=dp[1][i]={1e9,-1e9};
    for(i=1;i<=n<<1;i++)cin>>b[i];
    for(i=1;i<=n<<1;i++)ar[0][i]=a[i],ar[1][i]=b[i];
    dp[0][1]={1,1};
    dp[1][1]={0,0};
    for(i=2;i<=n<<1;i++){
        mi=1e9,ma=-1e9;
        if(a[i-1]<=a[i])mi=min(mi,dp[0][i-1].first);
        if(b[i-1]<=a[i])mi=min(mi,dp[1][i-1].first);
        dp[0][i].first=mi+1;
        if(a[i-1]<=a[i])ma=max(ma,dp[0][i-1].second);
        if(b[i-1]<=a[i])ma=max(ma,dp[1][i-1].second);
        dp[0][i].second=ma+1;
        mi=1e9,ma=-1e9;
        if(a[i-1]<=b[i])mi=min(mi,dp[0][i-1].first);
        if(b[i-1]<=b[i])mi=min(mi,dp[1][i-1].first);
        dp[1][i].first=mi;
        if(a[i-1]<=b[i])ma=max(ma,dp[0][i-1].second);
        if(b[i-1]<=b[i])ma=max(ma,dp[1][i-1].second);
        dp[1][i].second=ma;
    }
    pos=-1;
    if(dp[0][n<<1].first<=n&&n<=dp[0][n<<1].second)pos=0;
    else if(dp[1][n<<1].first<=n&&n<=dp[1][n<<1].second)pos=1;
    else{
        cout<<-1;
        return 0;
    }
    now=n;
    for(i=n<<1;i>0;i--){
        ans+='A'+pos;
        now-=(!pos);
        if(ar[pos][i]>=ar[0][i-1]&&dp[0][i-1].first<=now&&now<=dp[0][i-1].second)pos=0;
        else pos=1;
    }
    reverse(ans.begin(),ans.end());
    cout<<ans;
    return 0;
}

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