제출 #789082

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
789082		1075508020060209tc	Building 4 (JOI20_building4)	C++14	0 / 100	1 ms	340 KiB

building4

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,popcnt,sse4,abm")
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define X first
#define Y second
int n;
int ar[1000006];
int br[1000006];
pair<int,int>dp[2][1000006];
int ans[1000006];
signed main(){
cin>>n;n*=2;
for(int i=1;i<=n;i++){
    cin>>ar[i];
}
for(int i=1;i<=n;i++){
    cin>>br[i];
}
dp[0][1]={0,0};
dp[1][1]={1,1};
for(int i=2;i<=n;i++){
    pair<int,int>a={1e9,-1e9};pair<int,int>b={1e9,-1e9};
    if(ar[i]>=ar[i-1]){
        a=dp[0][i-1];
    }
    if(ar[i]>=br[i-1]){
        a={min(dp[1][i-1].first,a.first),max(dp[1][i-1].second,a.second)};
    }
    if(br[i]>=ar[i-1]){
        b=dp[0][i-1];
        b.first++;b.second++;
    }
    if(br[i]>=br[i-1]){
        b={min(dp[1][i-1].first+1,b.first),max(dp[1][i-1].second+1,b.second)};
    }
    
    if(a.second<b.first-1||b.second<a.first-1){return 0;}
    
    dp[1][i]=b;
    dp[0][i]=a;
}



int bcnt=0;int lst=1e18;
for(int i=n;i>=1;i--){
    if(br[i]<=lst&&n/2-bcnt>=dp[1][i].first&&n/2-bcnt<=dp[1][i].second){
        ans[i]=1;
        bcnt++;
        lst=br[i];
    }else{
        if(ar[i]>lst){cout<<-1;return 0;}
        ans[i]=0;
        lst=ar[i];

    }
}
if(bcnt!=n/2){cout<<-1;return 0;}


for(int i=1;i<=n;i++){
    if(ans[i]==0){
        cout<<"A";
    }else{
        cout<<"B";
    }
}

}

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