Submission #234284

#	Time	Username	Problem	Language	Result	Execution time	Memory
234284		aggu_01000101	Building 4 (JOI20_building4)	C++14	100 / 100	1251 ms	53896 KiB

building4

#include <bits/stdc++.h>
#define INF 10000000000000000
#define MOD 1000000017
#define mid(l, u) ((l+u)/2)
#define rchild(i) (i*2 + 2)
#define lchild(i) (i*2 + 1)
#define rr mt_rand()
#define int long long
using namespace std;
signed main(){
    int n;
    cin>>n;
    n*=2;
    int a[n][2];
    for(int i = 0;i<n;i++) cin>>a[i][0];
    for(int i = 0;i<n;i++) cin>>a[i][1];
    pair<int, int> dp[n][2]; //min number of A's, max number of A's
    dp[0][0] = {1, 1};
    dp[0][1] = {0, 0};
    for(int i = 1;i<n;i++){
        for(int j = 0;j<2;j++){
            dp[i][j] = make_pair(INF, -1);
            if(a[i-1][0]<=a[i][j]){
                dp[i][j].first = min(dp[i][j].first, dp[i-1][0].first + (j==0));
                dp[i][j].second = max(dp[i][j].second, dp[i-1][0].second + (j==0));
            }
            if(a[i-1][1]<=a[i][j]){
                dp[i][j].first = min(dp[i][j].first, dp[i-1][1].first + (j==0));
                dp[i][j].second = max(dp[i][j].second, dp[i-1][1].second + (j==0));
            }
        }
    }
    /*for(int i = 0;i<n;i++){
        cout<<i<<" "<<dp[i][0].first<<" "<<dp[i][0].second<<" "<<dp[i][1].first<<" "<<dp[i][1].second<<endl;
    }*/
    int req = n/2;
    int maxn = INF;
    stack<char> st;
    bool found = false;
    for(int i = n-1;i>=0;i--){
        found = false;
        for(int j = 0;j<2 && !found;j++){
            if(dp[i][j].first>req || dp[i][j].second<req || a[i][j]>maxn) continue;
            maxn = a[i][j];
            req-=(j==0);
            st.push((j==0)?'A':'B');
            found = true;
        }
        if(!found){
            break;
        }
    }
    if(!found){
        cout<<-1<<endl;
        return 0;
    }
    while(!st.empty()){
        cout<<st.top();
        st.pop();
    }
    cout<<endl;
}
//l, mid(l, r) || l+1, r
//

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