Submission #1013898

#	Time	Username	Problem	Language	Result	Execution time	Memory
1013898		Baytoro	Building 4 (JOI20_building4)	C++17	100 / 100	184 ms	58704 KiB

building4

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define fr first
#define sc second
#define int ll
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
int n,m;
const int N=1e6+5;
pair<int,int> dp[N][2];
void solve() {
    int n;cin>>n;
    vector<int> a(2*n+1),b(2*n+1);
    for(int i=1;i<=2*n;i++) cin>>a[i];
    for(int i=1;i<=2*n;i++) cin>>b[i];

    for(int i=1;i<=2*n;i++) dp[i][0]=dp[i][1]={-1,-1};
    dp[1][0]={1,1};
    dp[1][1]={0,0};
    for(int i=2;i<=2*n;i++) {
        if(a[i]>=a[i-1] && dp[i-1][0].fr!=-1) {
            if(dp[i][0].fr==-1) {
                dp[i][0].fr=dp[i-1][0].fr+1;
                dp[i][0].sc=dp[i-1][0].sc+1;
            }
            else {
                dp[i][0].fr=min(dp[i][0].fr,dp[i-1][0].fr+1);
                dp[i][0].sc=max(dp[i][0].sc,dp[i-1][0].sc+1);
            }
        }

        if(a[i]>=b[i-1] && dp[i-1][1].fr!=-1) {
            if(dp[i][0].fr==-1) {
                dp[i][0].fr=dp[i-1][1].fr+1;
                dp[i][0].sc=dp[i-1][1].sc+1;
            }
            else {
                dp[i][0].fr=min(dp[i][0].fr,dp[i-1][1].fr+1);
                dp[i][0].sc=max(dp[i][0].sc,dp[i-1][1].sc+1);
            }
        }

        if(b[i]>=a[i-1] && dp[i-1][0].fr!=-1) {
            if(dp[i][1].fr==-1) {
                dp[i][1].fr=dp[i-1][0].fr;
                dp[i][1].sc=dp[i-1][0].sc;
            }
            else {
                dp[i][1].fr=min(dp[i][1].fr,dp[i-1][0].fr);
                dp[i][1].sc=max(dp[i][1].sc,dp[i-1][0].sc);
            }
        }

        if(b[i]>=b[i-1] && dp[i-1][1].fr!=-1) {
            if(dp[i][1].fr==-1) {
                dp[i][1].fr=dp[i-1][1].fr;
                dp[i][1].sc=dp[i-1][1].sc;
            }
            else {
                dp[i][1].fr=min(dp[i][1].fr,dp[i-1][1].fr);
                dp[i][1].sc=max(dp[i][1].sc,dp[i-1][1].sc);
            }
        }
    }

    //for(int i=1;i<=2*n;i++) {
    //    cout<<dp[i][0].fr<<' '<<dp[i][0].sc<<"    "<<dp[i][1].fr<<' '<<dp[i][1].sc<<endl;
    //}

    if(dp[2*n][0].fr<=n && dp[2*n][0].sc>=n) {
        vector<bool> ans;
        int cur=n,t=0;
        for(int i=2*n;i>0;i--) {
            if(t==0) {cur--;ans.pb(0);}
            else ans.pb(1);

            if(i==1) break;

            if(t==0 ) {
                if(dp[i-1][0].fr<=cur && dp[i-1][0].sc>=cur && a[i]>=a[i-1]) {
                    t=0;
                }
                else if(dp[i-1][1].fr<=cur && dp[i-1][1].sc>=cur && a[i]>=b[i-1]) {
                    t=1;
                }
            }
            else {
                if(dp[i-1][0].fr<=cur && dp[i-1][0].sc>=cur && b[i]>=a[i-1]) {
                    t=0;
                }
                else if(dp[i-1][1].fr<=cur && dp[i-1][1].sc>=cur && b[i]>=b[i-1]) {
                    t=1;
                }
            }
        }
        for(int i=2*n-1;i>=0;i--) {
            if(ans[i]==0) cout<<'A';
            else cout<<'B';
        }
    }
    else if(dp[2*n][1].fr<=n && dp[2*n][1].sc>=n) {
        vector<bool> ans;
        int cur=n,t=1;
        for(int i=2*n;i>0;i--) {
            if(t==0) {cur--;ans.pb(0);}
            else ans.pb(1);

            if(i==1) break;
            if(t==0 ) {
                if(dp[i-1][0].fr<=cur && dp[i-1][0].sc>=cur && a[i]>=a[i-1]) {
                    t=0;
                }
                else if(dp[i-1][1].fr<=cur && dp[i-1][1].sc>=cur && a[i]>=b[i-1]) {
                    t=1;
                }
            }
            else {
                if(dp[i-1][0].fr<=cur && dp[i-1][0].sc>=cur && b[i]>=a[i-1]) {
                    t=0;
                }
                else if(dp[i-1][1].fr<=cur && dp[i-1][1].sc>=cur && b[i]>=b[i-1]) {
                    t=1;
                }
            }
        }
        for(int i=2*n-1;i>=0;i--) {
            if(ans[i]==0) cout<<'A';
            else cout<<'B';
        }
    }
    else cout<<-1<<endl;
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int t=1;//cin>>t;
    while(t--){
        solve();
    }
}
//#endif

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