Submission #337102

#	Time	Username	Problem	Language	Result	Execution time	Memory
337102		rocks03	Building 4 (JOI20_building4)	C++14	100 / 100	290 ms	69056 KiB

building4

//#pragma GCC target("avx2")
//#pragma GCC optimization("O3")
//#pragma GCC optimization("unroll-loops")
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define ff first
#define ss second
#define pb push_back
#define SZ(x) ((int)(x).size())
#define all(x) x.begin(), x.end()
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int MAXN = 1e6+100;
int N, a[MAXN], b[MAXN];
struct state{
    bool good;
    int l[2], r[2];
} dp[2][MAXN];

void solve(){
    cin >> N;
    N = 2 * N;
    for(int i = 0; i < N; i++){
        cin >> a[i];
    }
    for(int i = 0; i < N; i++){
        cin >> b[i];
    }
    state base; base.good = false;
    base.l[0] = base.l[1] = MAXN;
    base.r[0] = base.r[1] = -1;
    dp[0][0].good = dp[1][0].good = true;
    dp[0][0].l[0] = dp[0][0].r[0] = 1;
    dp[0][0].l[1] = dp[0][0].r[1] = 0;
    dp[1][0].l[0] = dp[1][0].r[0] = 0;
    dp[1][0].l[1] = dp[1][0].r[1] = 1;
    for(int i = 1; i < N; i++){
        if(max(a[i], b[i]) < min(a[i-1], b[i-1])){
            cout << "-1";
            return;
        }
        dp[0][i] = dp[1][i] = base;
        if(a[i] >= a[i-1] && dp[0][i-1].good){
            dp[0][i].good = true;
            dp[0][i].l[0] = min(dp[0][i].l[0], dp[0][i-1].l[0] + 1);
            dp[0][i].r[0] = max(dp[0][i].r[0], dp[0][i-1].r[0] + 1);
            dp[0][i].l[1] = min(dp[0][i].l[1], dp[0][i-1].l[1]);
            dp[0][i].r[1] = max(dp[0][i].r[1], dp[0][i-1].r[1]);
        }
        if(a[i] >= b[i-1] && dp[1][i-1].good){
            dp[0][i].good = true;
            dp[0][i].l[0] = min(dp[0][i].l[0], dp[1][i-1].l[0] + 1);
            dp[0][i].r[0] = max(dp[0][i].r[0], dp[1][i-1].r[0] + 1);
            dp[0][i].l[1] = min(dp[0][i].l[1], dp[1][i-1].l[1]);
            dp[0][i].r[1] = max(dp[0][i].r[1], dp[1][i-1].r[1]);
        }
        if(b[i] >= a[i-1] && dp[0][i-1].good){
            dp[1][i].good = true;
            dp[1][i].l[0] = min(dp[1][i].l[0], dp[0][i-1].l[0]);
            dp[1][i].r[0] = max(dp[1][i].r[0], dp[0][i-1].r[0]);
            dp[1][i].l[1] = min(dp[1][i].l[1], dp[0][i-1].l[1] + 1);
            dp[1][i].r[1] = max(dp[1][i].r[1], dp[0][i-1].r[1] + 1);
        }
        if(b[i] >= b[i-1] && dp[1][i-1].good){
            dp[1][i].good = true;
            dp[1][i].l[0] = min(dp[1][i].l[0], dp[1][i-1].l[0]);
            dp[1][i].r[0] = max(dp[1][i].r[0], dp[1][i-1].r[0]);
            dp[1][i].l[1] = min(dp[1][i].l[1], dp[1][i-1].l[1] + 1);
            dp[1][i].r[1] = max(dp[1][i].r[1], dp[1][i-1].r[1] + 1);
        }
        if(!dp[0][i].good && !dp[1][i].good){
            cout << "-1";
            return;
        }
    }
    string ans = "";
    int A = N / 2, B = N / 2, mx = INT_MAX;
    for(int i = N - 1; i >= 0; i--){
        if(a[i] > mx && b[i] > mx){
            cout << "-1";
            return;
        }
        if(A == 0){
            if(b[i] <= mx){
                B--;
                ans += 'B';
                mx = b[i];
                continue;
            }
            cout << "-1";
            return;
        }
        if(B == 0){
            if(a[i] <= mx){
                A--;
                ans += 'A';
                mx = a[i];
                continue;
            }
            cout << "-1";
            return;
        }
        if(a[i] <= mx){
            if(dp[0][i].l[0] <= A && A <= dp[0][i].r[0] && dp[0][i].l[1] <= B && B <= dp[0][i].r[1]){
                A--;
                ans += 'A';
                mx = a[i];
                continue;
            }
        }
        if(b[i] <= mx){
            if(dp[1][i].l[0] <= A && A <= dp[1][i].r[0] && dp[1][i].l[1] <= B && B <= dp[1][i].r[1]){
                B--;
                ans += 'B';
                mx = b[i];
                continue;
            }
        }
        cout << "-1";
        return;
    }
    reverse(all(ans));
    cout << ans;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
    return 0;
}

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