Submission #283133

#	Time	Username	Problem	Language	Result	Execution time	Memory
283133		mosiashvililuka	Building 4 (JOI20_building4)	C++14	100 / 100	343 ms	44664 KiB

building4

#include<bits/stdc++.h>
using namespace std;
int a,b,c,d,e,i,j,ii,jj,zx,xc,dpmn[1000009][2],dpmx[1000009][2],f[1000009],g[1000009],kl[1000009][2];
char pas[1000009];
int main(){
    ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>a;
    a*=2;
    for(i=1; i<=a; i++) cin>>f[i];
    for(i=1; i<=a; i++) cin>>g[i];
    for(i=0; i<=a; i++){
        for(j=0; j<=1; j++){
            dpmn[i][j]=a+3;
            dpmx[i][j]=0; 
        }
    }
    dpmn[0][0]=0;dpmx[0][0]=0;
    dpmn[0][1]=0;dpmx[0][1]=0;
    for(i=1; i<=a; i++){
        kl[i][0]=f[i];kl[i][1]=g[i];
        if(f[i]>=f[i-1]){
            dpmn[i][0]=min(dpmn[i][0],dpmn[i-1][0]+1);
            dpmx[i][0]=max(dpmx[i][0],dpmx[i-1][0]+1);
        }
        if(f[i]>=g[i-1]){
            dpmn[i][0]=min(dpmn[i][0],dpmn[i-1][1]+1);
            dpmx[i][0]=max(dpmx[i][0],dpmx[i-1][1]+1);
        }
        if(g[i]>=f[i-1]){
            dpmn[i][1]=min(dpmn[i][1],dpmn[i-1][0]);
            dpmx[i][1]=max(dpmx[i][1],dpmx[i-1][0]);
        }
        if(g[i]>=g[i-1]){
            dpmn[i][1]=min(dpmn[i][1],dpmn[i-1][1]);
            dpmx[i][1]=max(dpmx[i][1],dpmx[i-1][1]);
        }
    }
    j=-1;
    if(dpmn[a][0]<=a/2&&a/2<=dpmx[a][0]){
        j=0;
    }
    if(dpmn[a][1]<=a/2&&a/2<=dpmx[a][1]){
        j=1;
    }
    if(j==-1){
        cout<<-1;
        return 0;
    }
    //cout<<j<<endl;
    zx=a/2;
    for(i=a; i>=1; i--){
        if(j==-1){
            cout<<-1;
            return 0;
        }
        xc=-1;
        if(j==0) jj=1; else jj=0;
        if(j==0) zx--;
        if(j==0) pas[i]='A'; else pas[i]='B';
        if(kl[i][j]>=kl[i-1][j]&&dpmn[i-1][j]<=zx&&zx<=dpmx[i-1][j]){
            xc=j;
        }
        if(kl[i][j]>=kl[i-1][jj]&&dpmn[i-1][jj]<=zx&&zx<=dpmx[i-1][jj]){
            xc=jj;
        }
        j=xc;
    }
    for(i=1; i<=a; i++) cout<<pas[i];
    return 0;
}

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