Submission #282964

#	Time	Username	Problem	Language	Result	Execution time	Memory
282964		wildturtle	Building 4 (JOI20_building4)	C++17	100 / 100	1757 ms	115820 KiB

building4

#include<bits/stdc++.h>
using namespace std;
long long a,b,c,d,i,e,f,g,n,m,k,l,wina,darch;
long long A[5][1000006],minn[1000006][5],maxx[1000006][5];
string s;
int main() {
    cin>>n;
    n*=2;
    for(long long i=1;i<=2;i++) {
        for(long long j=1;j<=n;j++) {
            cin>>A[i][j];
            minn[j][i]=1000000009;
        }
    }
    //cout<<"*";
    minn[1][1]=1; maxx[1][1]=1;
    minn[1][2]=0; maxx[1][2]=0;
    for(long long i=1;i<=n;i++) {
        for(long long j=1;j<=2;j++) {
        	//cout<<i<<" "<<j<<endl;
            if(A[j][i]>=A[1][i-1]) {
                //if(j==1 && i==2) cout<<minn[i][j]<<"-"<<minn[i-1][1]<<endl;
                minn[i][j]=min(minn[i][j],minn[i-1][1]+(j==1 ? 1:0));
                maxx[i][j]=max(maxx[i][j],maxx[i-1][1]+(j==1 ? 1:0));
            }
            if(A[j][i]>=A[2][i-1]) {
                //if(j==1 & i==2) cout<<minn[i][j]<<"-"<<minn[i-1][2]<<endl;
                minn[i][j]=min(minn[i][j],minn[i-1][2]+(j==1 ? 1:0));
                maxx[i][j]=max(maxx[i][j],maxx[i-1][2]+(j==1 ? 1:0));                
            }
        }
    }
    /*for(long long i=1;i<=n;i++) {
        for(long long j=1;j<=2;j++) {
            cout<<"{"<<minn[i][j]<<" "<<maxx[i][j]<<"}";
        }
        cout<<endl;
    }
    cout<<"*";*/
    darch=n/2;
    wina=1000000009;
    for(long long i=n;i>=1;i--) {
        for(long long j=1;j<=2;j++) {
            if(A[j][i]<=wina && minn[i][j]<=darch && darch<=maxx[i][j]) {
                wina=A[j][i];
                darch-=(j==1 ? 1:0);
                s+=(j==1 ? 'A':'B');
                k=1;
                break;
            }
        }
        if(k==0) {cout<<-1; return 0; }
    }
    reverse(s.begin(),s.end());
    cout<<s;
}

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