Submission #894686

#	Time	Username	Problem	Language	Result	Execution time	Memory
894686		box	Building 4 (JOI20_building4)	C++17	100 / 100	201 ms	45396 KiB

building4

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

#define ar array
#define sz(v) int(std::size(v))
using i64 = long long;
using range = ar<int, 2>;

const range unit{-1, -1};

range shift(const range one, int c) {
    if (one == unit) return one;
    return {one[0] + c, one[1] + c};
}

range operator+(const range one, const range two) {
    if (one == unit) return two;
    if (two == unit) return one;
    return {min(one[0], two[0]), max(one[1], two[1])};
}

bool can(const range one, int x) {
    return one[0] <= x && one[1] >= x;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N;
    cin >> N;
    int A[N * 2 + 1], B[N * 2 + 1];
    A[0] = B[0] = 0;
    for (int i = 1; i <= N * 2; i++) cin >> A[i];
    for (int i = 1; i <= N * 2; i++) cin >> B[i];
    /*
    auto solve = [&]() {
        ar<int, 2> dp{1, 0};
        for (int i = 1; i < N * 2; i++) {
            ar<int, 2> ndp{-(N * 2), -(N * 2)};
            if (A[i - 1] <= A[i]) ndp[0] = max(ndp[0], dp[0] + 1);
            if (B[i - 1] <= A[i]) ndp[0] = max(ndp[0], dp[1] + 1);
            if (A[i - 1] <= B[i]) ndp[1] = max(ndp[1], dp[0]);
            if (B[i - 1] <= B[i]) ndp[1] = max(ndp[1], dp[1]);
            dp = ndp;
        }
        return max(dp[0], dp[1]);
    };
    bool ok = 1;
    ok &= solve() >= N;
    swap(A, B);
    ok &= solve() >= N;
    cout << (ok ? "YES\n" : "NO\n");
    */
    range f[N * 2 + 1][2];
    f[0][0] = f[0][1] = {0, 0};
    for (int i = 1; i <= N * 2; i++) {
        f[i][0] = f[i][1] = unit;
        if (A[i - 1] <= A[i]) f[i][0] = f[i][0] + shift(f[i - 1][0], 1);
        if (B[i - 1] <= A[i]) f[i][0] = f[i][0] + shift(f[i - 1][1], 1);
        if (A[i - 1] <= B[i]) f[i][1] = f[i][1] + f[i - 1][0];
        if (B[i - 1] <= B[i]) f[i][1] = f[i][1] + f[i - 1][1];
    }
    for (int t : {0, 1}) if (can(f[N * 2][t], N)) {
        string S;
        int i = N * 2, c = N;
        while (i > 0) {
            S += char('A' + t);
            c -= t ^ 1;
            if (A[i - 1] <= (t ? B : A)[i] && can(f[i - 1][0], c)) {
                t = 0;
                i--;
            } else if (B[i - 1] <= (t ? B : A)[i] && can(f[i - 1][1], c)) {
                t = 1;
                i--;
            } else assert(false);
        }
        reverse(begin(S), end(S));
        cout << S << '\n';
        return 0;
    }
    cout << "-1\n";
}

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