Submission #237178

#	Time	Username	Problem	Language	Result	Execution time	Memory
237178		hackermub	Building 4 (JOI20_building4)	C++17	100 / 100	358 ms	50252 KiB

building4

#include<bits/stdc++.h>
using namespace std;

#define int long long
#define pii pair<int,int>
#define INF (int)1e18
#define all(v) v.begin(), v.end()

const int MAXN =1e6+7;
int n;
int dp[MAXN][2][2]; // min and max A if ith bit=j
int ara[2][MAXN];

void min_self(int &x,int y){
    x=min(x,y);
}

void max_self(int &x,int y){
    x=max(x,y);
}

int32_t main(){
    ios_base::sync_with_stdio(false),cin.tie(),cout.tie();
    // If you hack my code, you are gay
    cin>>n;
    int N=2*n;
    for(auto x:{0,1}){
        for(int i=0;i<N;i++){
             cin>>ara[x][i];
             dp[i][x][0]=INF;
             dp[i][x][1]=0;
        }
    }
    ara[0][N]=INF;
    dp[0][0][0]=dp[0][0][1]=1;
    dp[0][1][0]=dp[0][1][1]=0;
    for(int i=1;i<N;i++){
        for(auto x:{0,1}){
            if(ara[x][i-1]<=ara[0][i]){
                min_self(dp[i][0][0],dp[i-1][x][0]+1);
                max_self(dp[i][0][1],dp[i-1][x][1]+1);
            }
            if(ara[x][i-1]<=ara[1][i]){
                min_self(dp[i][1][0],dp[i-1][x][0]);
                max_self(dp[i][1][1],dp[i-1][x][1]);
            }
        }
    }
    string ans;
    int rem=n;
    int last=0;
    for(int i=N-1;i>=0;i--){
        char ch='A';
        if(dp[i][0][0]<=rem && rem<=dp[i][0][1] && ara[0][i]<=ara[last][i+1]){
            rem--;
            last=0;
        }else if(dp[i][1][0]<=rem && rem<=dp[i][1][1] && ara[1][i]<=ara[last][i+1]){
            last=1;
            ch='B';
        }else{
            cout<<-1;
            return 0;
        }
        ans.push_back(ch);
    }
    reverse(all(ans));
    cout<<ans;
    return 0;
}

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