Submission #1291242

#	Time	Username	Problem	Language	Result	Execution time	Memory
1291242		haha	Building 4 (JOI20_building4)	C++20	11 / 100	34 ms	2272 KiB

building4

#include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
#define ll long long
const int maxn=5e5+5;
const ll MOD=1e9+7;
const int base=31;

int n;
int a[maxn],b[maxn];
pair<int,int> dp[maxn][2];
// 0 A
// 1 B
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n;
    for(int i=1;i<=2*n;i++) cin>>a[i];
    for(int i=1;i<=2*n;i++) cin>>b[i];
    dp[0][0]={0,0};
    dp[0][1]={0,0};
    for(int i=1;i<=2*n;i++){
        dp[i][0]={1e9,0};
        dp[i][1]={1e9,0};
        if(a[i]>=a[i-1]){
            dp[i][0].f=min(dp[i][0].f,dp[i-1][0].f+1);
            dp[i][0].s=max(dp[i][0].s,dp[i-1][0].s+1);
        }
        if(a[i]>=b[i-1]){
            dp[i][0].f=min(dp[i][0].f,dp[i-1][1].f+1);
            dp[i][0].s=max(dp[i][0].s,dp[i-1][1].s+1);
        }
        if(b[i]>=b[i-1]){
            dp[i][1].f=min(dp[i][1].f,dp[i-1][1].f);
            dp[i][1].s=max(dp[i][1].s,dp[i-1][1].s);
        }
        if(b[i]>=a[i-1]){
            dp[i][1].f=min(dp[i][1].f,dp[i-1][0].f);
            dp[i][1].s=max(dp[i][1].s,dp[i-1][0].s);
        }
    }
    bool check=false;
    int lst;
    if(dp[2*n][0].f<=n&&n<=dp[2*n][0].s){
        check=true;
        lst=0;
    }
    if(dp[2*n][1].f<=n&&n<=dp[2*n][1].s){
        check=true;
        lst=1;
    }
    if(!check){
        cout<<-1;
        return 0;
    }
    int cnt=n;
    string ans;
    for(int i=2*n;i>=1;i--){
        if(lst==0){
            ans+='A';
            cnt--;
        }
        else ans+='B';
        int prev=-1;
        if(lst==0){
            if(a[i]>=a[i-1]&&dp[i-1][0].f<=cnt&&cnt<=dp[i-1][0].s) prev=0;
            else if(a[i]>=b[i-1]&&dp[i-1][1].f<=cnt&&cnt<=dp[i-1][1].s) prev=1;
        }
        else{
            if(b[i]>=a[i-1]&&dp[i-1][0].f<=cnt&&cnt<=dp[i-1][0].s) prev=0;
            else if(b[i]>=b[i-1]&&dp[i-1][1].f<=cnt&&cnt<=dp[i-1][1].s) prev=1;
        }
        if(prev==-1){
            cout<<-1;
            return 0;
        }
        lst=prev;
    }
    reverse(ans.begin(),ans.end());
    cout<<ans;
}

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