Submission #1099566

#	Time	Username	Problem	Language	Result	Execution time	Memory
1099566		imarn	Building 4 (JOI20_building4)	C++14	100 / 100	191 ms	63828 KiB

building4

#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define plx pair<ll,int>
#define f first
#define s second
#define pb push_back
#define all(x) x.begin(),x.end()
#define vi vector<int>
#define vl vector<ll>
#define vvi vector<vi>
using namespace std;
const ll inf=123456789,mxn=1e6+5;
int dpl[2][mxn]{0},dpr[2][mxn]{0},a[mxn],b[mxn];
int prl[2][mxn],prr[2][mxn];
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    int n;cin>>n;
    for(int i=0;i<2*n;i++)cin>>a[i];
    for(int i=0;i<2*n;i++)cin>>b[i];
    dpl[0][0]=1;dpl[1][0]=0;prl[0][0]=prl[1][0]=-1;
    for(int i=1;i<2*n;i++){
        dpl[0][i]=dpl[1][i]=-1e9;
        if(a[i]>=a[i-1]&&dpl[0][i]<dpl[0][i-1]+1)dpl[0][i]=dpl[0][i-1]+1,prl[0][i]=0;
        if(a[i]>=b[i-1]&&dpl[0][i]<dpl[1][i-1]+1)dpl[0][i]=dpl[1][i-1]+1,prl[0][i]=1;
        if(b[i]>=a[i-1]&&dpl[1][i]<dpl[0][i-1])dpl[1][i]=dpl[0][i-1],prl[1][i]=0;
        if(b[i]>=b[i-1]&&dpl[1][i]<dpl[1][i-1])dpl[1][i]=dpl[1][i-1],prl[1][i]=1;
    }dpr[0][2*n-1]=0,dpr[1][2*n-1]=1;prr[0][2*n-1]=prr[1][2*n-1]=-1;
    for(int i=2*n-2;i>=0;i--){
        dpr[0][i]=dpr[1][i]=-1e9;
        if(a[i+1]>=a[i]&&dpr[0][i]<dpr[0][i+1])dpr[0][i]=dpr[0][i+1],prr[0][i]=0;
        if(a[i+1]>=b[i]&&dpr[1][i]<dpr[0][i+1]+1)dpr[1][i]=dpr[0][i+1]+1,prr[1][i]=0;
        if(b[i+1]>=a[i]&&dpr[0][i]<dpr[1][i+1])dpr[0][i]=dpr[1][i+1],prr[0][i]=1;
        if(b[i+1]>=b[i]&&dpr[1][i]<dpr[1][i+1]+1)dpr[1][i]=dpr[1][i+1]+1,prr[1][i]=1;
    }int ans[2*n]={0};int mem1=-1,mem2=-1,mem3=-1;
    for(int i=0;i<2*n-1;i++){
        if(a[i]<=a[i+1]&&dpl[0][i]+2*n-1-i-dpr[0][i+1]==n&&dpl[0][i]>=0&&dpr[0][i+1]>=0)mem1=i,mem2=0,mem3=0;
        if(b[i]<=a[i+1]&&dpl[1][i]+2*n-1-i-dpr[0][i+1]==n&&dpl[1][i]>=0&&dpr[0][i+1]>=0)mem1=i,mem2=1,mem3=0;
        if(a[i]<=b[i+1]&&dpl[0][i]+2*n-1-i-dpr[1][i+1]==n&&dpl[0][i]>=0&&dpr[1][i+1]>=0)mem1=i,mem2=0,mem3=1;
        if(b[i]<=b[i+1]&&dpl[1][i]+2*n-1-i-dpr[1][i+1]==n&&dpl[1][i]>=0&&dpr[1][i+1]>=0)mem1=i,mem2=1,mem3=1;
        if(mem1!=-1){
            int cur=mem1,c=mem2;
            while(cur>=0){
                ans[cur]=c;
                c=prl[c][cur];cur--;
            }cur=mem1+1,c=mem3;
            while(cur<=2*n-1){
                ans[cur]=c;
                c=prr[c][cur];cur++;
            }
            for(int i=0;i<2*n;i++){
                if(ans[i])cout<<'B';
                else cout<<'A';
            }return 0;
        }
    }cout<<mem1;
}

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