Submission #331982

#	Time	Username	Problem	Language	Result	Execution time	Memory
331982		12tqian	Building 4 (JOI20_building4)	C++17	100 / 100	288 ms	45792 KiB

building4

#include <bits/stdc++.h>

int main() {
    using namespace std;
    ios_base::sync_with_stdio(0);
    int n; cin >> n;
    vector<int> a(2 * n), b(2 * n);
    for (int i = 0; i < 2 * n; i++)
        cin >> a[i];
    for (int i = 0; i < 2 * n; i++)
        cin >> b[i];
    // the dp states 
    vector<array<pair<int, int>, 2>> dp(2 * n);
    // 0 stands for A, 1 stands for B
    for (int i = 0; i < 2 * n; i++) 
        for (int j = 0; j < 2; j++) 
            dp[i][j].first = dp[i][j].second = -1;
    dp[0][0] = {1, 1};
    dp[0][1] = {0, 0};
    for (int i = 1; i < 2 * n; i++) {
        // if i end in A
        if (a[i] >= a[i - 1] && dp[i - 1][0].first != -1) {
            dp[i][0] = dp[i - 1][0];
            dp[i][0].first++;
            dp[i][0].second++;
        }
        if (a[i] >= b[i - 1] && dp[i - 1][1].first != -1) {
            if (dp[i][0].first == -1) {
                dp[i][0] = dp[i - 1][1];
                dp[i][0].first++;
                dp[i][0].second++;
            } else {
                dp[i][0].first = min(dp[i][0].first, dp[i - 1][1].first + 1);
                dp[i][0].second = max(dp[i][0].second, dp[i - 1][1].second + 1);
            }
        }
        if (b[i] >= a[i - 1] && dp[i - 1][0].first != -1) {
            dp[i][1] = dp[i - 1][0];
        }
        if (b[i] >= b[i - 1] && dp[i - 1][1].first != -1) {
            if (dp[i][1].first == -1) {
                dp[i][1] = dp[i - 1][1];
            } else { 
                dp[i][1].first = min(dp[i][1].first, dp[i - 1][1].first);
                dp[i][1].second = max(dp[i][1].second, dp[i - 1][1].second);
            }
        }
    }
    auto in = [&](pair<int, int> p, int x) -> bool {
        return p.first <= x && x <= p.second;
    };
    bool ok1 = in(dp[2 * n - 1][0], n);
    bool ok2 = in(dp[2 * n - 1][1], n);
    if (!ok1 && !ok2) {
        cout << -1 << '\n';
    } else {
        int ci = 2 * n - 1, cj, cv = n;
        if (ok1) {
            cj = 0;
        } else { 
            cj = 1;
        }
        string ans = "";
        while (true) {
            ans += (char) ('A' + cj);
            if (ci == 0)
                break;
            if (cj == 0) {
                if (a[ci - 1] <= a[ci] && in(dp[ci - 1][0], cv - 1)) {
                    cj = 0;
                    cv--;
                } else {
                    cj = 1;
                    cv--;
                }
            } else { 
                if (a[ci - 1] <= b[ci] && in(dp[ci - 1][0], cv)) { 
                    cj = 0;
                } else {
                    cj = 1;
                }
            }
            ci--;
        }
        reverse(ans.begin(), ans.end());
        cout << ans << '\n';
    }
    return 0;
}

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