Submission #1341022

#TimeUsernameProblemLanguageResultExecution timeMemory
1341022Warinchai건물 4 (JOI20_building4)C++20
0 / 100
1 ms344 KiB
#include<bits/stdc++.h>
using namespace std;

int a[1000005][2];
int mx[1000005][2];
int mn[1000005][2];

int inf=1e9;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n;cin>>n;
    n=n*2;
    for(int i=1;i<=n;i++)cin>>a[i][0];
    for(int i=1;i<=n;i++)cin>>a[i][1];
    for(int i=1;i<=n;i++){
        mx[i][0]=mx[i][1]=-inf;
        mn[i][0]=mn[i][1]=inf;
    }
    mx[n][0]=mn[n][0]=1;
    mx[n][1]=mn[n][1]=-1;
    for(int i=n-1;i>=1;i--){
        for(int j=0;j<2;j++)for(int k=0;k<2;k++){
            if(a[i][j]<=a[i+1][k]){
                mx[i][j]=max(mx[i][j],mx[i+1][k]+(j?-1:1));
                mn[i][j]=min(mn[i][j],mn[i+1][k]+(j?-1:1));
            }
        }
    }
    string ans;
    int cnt=0;
    int can=1;
    //cerr<<"work\n";
    for(int i=0;i<n;i++){
        if(cnt+mx[i+1][0]>=0&&cnt+mn[i+1][0]<=0)ans.push_back('A'),cnt++;
        else if(cnt+mx[i+1][1]>=0&&cnt+mn[i+1][1]<=0)ans.push_back('B'),cnt--;
        else{
            can=0;
            break;
        }
    }
    if(can){
        cout<<ans;
    }else{
        cout<<"-1";
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...