Submission #1307439

#	Time	Username	Problem	Language	Result	Execution time	Memory
1307439		M_W_13	Building 4 (JOI20_building4)	C++20	100 / 100	172 ms	27964 KiB

building4

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
#define rep(i, n) for (int i = 0; i < (n); i++)
#define st first
#define nd second
#define pb push_back
#define pii pair<int, int>
#define pll pair<ll, ll>
#define all(a) a.begin(), a.end()

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n;
    cin >> n;
    int A[2 * n];
    int B[2 * n];
    rep(i, 2 * n) {
        cin >> A[i];
    }
    rep(i, 2 * n) {
        cin >> B[i];
    }
    pii T[2 * n][2];
    T[0][0] = {0, 0};
    T[0][1] = {1, 1};
    bool czy[2 * n][2];
    rep(i, 2 * n) {
        rep(c, 2) czy[i][c] = false;
    }
    rep(c, 2) czy[0][c] = true;
    for (int i = 1; i < (2 * n); i++) {
        if (A[i] >= A[i - 1] && czy[i - 1][0]) {
            czy[i][0] = true;
            T[i][0] = T[i - 1][0];
        }
        if (A[i] >= B[i - 1] && czy[i - 1][1]) {
            if (!czy[i][0]) T[i][0] = T[i - 1][1];
            czy[i][0] = true;
            T[i][0] = {min(T[i][0].st, T[i - 1][1].st), max(T[i][0].nd, T[i - 1][1].nd)};
        }
        if (B[i] >= A[i - 1] && czy[i - 1][0]) {
            czy[i][1] = true;
            T[i][1] = T[i - 1][0];
        }
        if (B[i] >= B[i - 1] && czy[i - 1][1]) {
            if (!czy[i][1]) T[i][1] = T[i - 1][1];
            czy[i][1] = true;
            T[i][1] = {min(T[i][1].st, T[i - 1][1].st), max(T[i][1].nd, T[i - 1][1].nd)};
        }
        T[i][1].st++;
        T[i][1].nd++;
    }
    int m = 2 * n - 1;
    bool spr = false;
    if (czy[m][0] && (T[m][0].st <= n && T[m][0].nd >= n)) {
        spr = true;
    }
    if (czy[m][1] && (T[m][1].st <= n && T[m][1].nd >= n)) {
        spr = true;
    }
    if (!spr) {
        cout << -1 << '\n';
        return 0;
    }
    int cnt = n;
    string s = "";
    int last = 1e9 + 1;
    for (int i = m; i >= 0; i--) {
        if ((last >= A[i]) && czy[i][0] && (T[i][0].st <= cnt && T[i][0].nd >= cnt)) {
            s += "A";
            last = A[i];
        }
        else if ((last >= B[i]) && czy[i][1] && (T[i][1].st <= cnt && T[i][1].nd >= cnt)) {
            s += "B";
            last = B[i];
            cnt--;
        }
    }
    reverse(all(s));
    cout << s << '\n';
    return 0;
}

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