Submission #1171673

#	Time	Username	Problem	Language	Result	Execution time	Memory
1171673		AlgorithmWarrior	Building 4 (JOI20_building4)	C++20	100 / 100	539 ms	56208 KiB

building4

#include <bits/stdc++.h>

using namespace std;

void minself(int& x,int val){
    if(x>val)
        x=val;
}

void maxself(int& x,int val){
    if(x<val)
        x=val;
}

int const MAX=1e6+5;
int n;
int mat[2][MAX];
int le[2][MAX],ri[2][MAX];

void read(){
    cin>>n;
    int i,j;
    for(i=0;i<2;++i)
        for(j=1;j<=2*n;++j)
            cin>>mat[i][j];
}

void get_dp(){
    int i,j;
    for(j=1;j<=2*n;++j)
        for(i=0;i<2;++i){
            le[i][j]=1e9;
            ri[i][j]=-1e9;
            int lin;
            for(lin=0;lin<2;++lin)
                if(mat[lin][j-1]<=mat[i][j]){
                    minself(le[i][j],le[lin][j-1]);
                    maxself(ri[i][j],ri[lin][j-1]);
                }
            if(i==0){
                ++le[i][j];
                ++ri[i][j];
            }
        }
}

void write_path(int lin,int col,int cnt){
    if(col==0)
        return;
    int i;
    for(i=0;i<2;++i)
        if(mat[i][col-1]<=mat[lin][col] && le[i][col-1]<=cnt-(lin==0) && cnt-(lin==0)<=ri[i][col-1]){
            write_path(i,col-1,cnt-(lin==0));
            break;
        }
    cout<<((lin==0)?'A':'B');
}

void write(){
    int i;
    for(i=0;i<2;++i)
        if(le[i][2*n]<=n && n<=ri[i][2*n]){
            write_path(i,2*n,n);
            return;
        }
    cout<<-1;
}

int main()
{
    read();
    get_dp();
    write();
    return 0;
}

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