Submission #232158

#	Time	Username	Problem	Language	Result	Execution time	Memory
232158		brcode	Building 4 (JOI20_building4)	C++14	100 / 100	1264 ms	48912 KiB

building4

#include <iostream>
#include <bits/stdc++.h>

using namespace std;
const int MAXN = 1e6+5;
int a[MAXN];
int b[MAXN];
int dpmax[MAXN][3];
int dpmin[MAXN][3];
int main(){
    int n;
    cin>>n;
    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++){
        for(int k=0;k<=1;k++){
            dpmin[i][k]  = 1e9;
        }
    }
    for(int i=1;i<=2*n;i++){
        for(int k=0;k<=1;k++){
            if(k){
                if(a[i-1]<=b[i]){
                    dpmin[i][k] = min(dpmin[i][k],dpmin[i-1][0]);
                }
                if(b[i-1]<=b[i]){
                    dpmin[i][k] = min(dpmin[i][k],dpmin[i-1][1]);
                }
                
            }else{
                if(a[i-1]<=a[i]){
                    dpmin[i][k] = min(dpmin[i][k],dpmin[i-1][0]+1);
                }
                if(b[i-1]<=a[i]){
                    dpmin[i][k] = min(dpmin[i][k],dpmin[i-1][1]+1);
                }
            }
          // 
        }
        
    }
    for(int i=1;i<=2*n;i++){
        for(int k=0;k<=1;k++){
            if(k){
                if(a[i-1]<=b[i]){
                    dpmax[i][k] = max(dpmax[i][k],dpmax[i-1][0]);
                }
                if(b[i-1]<=b[i]){
                    dpmax[i][k] = max(dpmax[i][k],dpmax[i-1][1]);
                }
            }else{
                if(a[i-1]<=a[i]){
                    dpmax[i][k] = max(dpmax[i][k],dpmax[i-1][0]+1);
                }
                if(b[i-1]<=a[i]){
                    dpmax[i][k] = max(dpmax[i][k],dpmax[i-1][1]+1);
                }
            }
           // cout<<i<<" "<<k<<" "<<dpmin[i][k]<<" "<<dpmax[i][k]<<endl;
        }
    }
    if((dpmin[2*n][0]<=n && dpmax[2*n][0]>=n)||(dpmin[2*n][1]<=n && dpmax[2*n][1]>=n)){
        string ans = "";
        int cnt = n;
        int lst = 1e9;
        for(int i=2*n;i>=1;i--){
            if((dpmin[i][0]<=cnt && dpmax[i][0]>=cnt) && cnt){
                if((dpmin[i][1]<=cnt && dpmax[i][1]>=cnt)){
                   if(lst == 0){
                       if(a[i]<=a[i+1]){
                           ans+='A';
                            lst = 0;
                            cnt--;
                       }else{
                           ans+='B';
                           lst = 1;
                       }
                   }else if(lst ==1){
                       if(a[i]<=b[i+1]){
                           ans+='A';
                           lst = 0;
                           cnt--;
                       }else{
                           ans+='B';
                           lst = 1;
                       }
                   }else{
                       ans+='A';
                        lst = 0;
                        cnt--;
                   }
                }else{
                    ans+='A';
                    lst = 0;
                    cnt--;
                }
            }else{
                ans+='B';
                lst = 1;
            }
            
        }
        reverse(ans.begin(),ans.end());
        cout<<ans<<endl;
    }else{
        cout<<-1<<endl;
    }
    
}

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