Submission #809857

#	Time	Username	Problem	Language	Result	Execution time	Memory
809857		vjudge1	건물 4 (JOI20_building4)	C++17	100 / 100	244 ms	48160 KiB

building4

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

int32_t main() {
        ios_base::sync_with_stdio(0);
        cin.tie(0);
        int n;
        cin >> n;
        n *= 2;
        vector<int> a(n + 1, 0), b(n + 1, 0);
        for (int i = 1; i <= n; i++) cin >> a[i];
        for (int i = 1; i <= n; i++) cin >> b[i];
        vector<vector<int>> dp_max(2, vector<int>(n + 1, -1));
        vector<vector<int>> dp_min(2, vector<int>(n + 1, n + 1));
        dp_max[0][0] = dp_max[1][0] = dp_min[0][0] = dp_min[1][0] = 0;
        for (int i = 0; i < n; i++) {
                if (a[i + 1] >= a[i]) {
                        if (dp_max[0][i] >= 0) dp_max[0][i + 1] = max(dp_max[0][i + 1], dp_max[0][i] + 1);
                        if (dp_min[0][i] <= n) dp_min[0][i + 1] = min(dp_min[0][i + 1], dp_min[0][i] + 1);
                }
                if (a[i + 1] >= b[i]) {
                        if (dp_max[1][i] >= 0) dp_max[0][i + 1] = max(dp_max[0][i + 1], dp_max[1][i] + 1);
                        if (dp_min[1][i] <= n) dp_min[0][i + 1] = min(dp_min[0][i + 1], dp_min[1][i] + 1);
                }
                if (b[i + 1] >= b[i]) {
                        if (dp_max[1][i] >= 0) dp_max[1][i + 1] = max(dp_max[1][i + 1], dp_max[1][i]);
                        if (dp_min[1][i] <= n) dp_min[1][i + 1] = min(dp_min[1][i + 1], dp_min[1][i]);
                }
                if (b[i + 1] >= a[i]) {
                        if (dp_max[0][i] >= 0) dp_max[1][i + 1] = max(dp_max[1][i + 1], dp_max[0][i]);
                        if (dp_min[0][i] <= n) dp_min[1][i + 1] = min(dp_min[1][i + 1], dp_min[0][i]);
                }
        }
        int cur = -1;
        for (int i = 0; i < 2; i++) {
                if (dp_max[i][n] < n / 2 || dp_min[i][n] > n / 2) continue;
                cur = i;
        }
        if (cur == -1) return cout << -1, 0;
        string ans = "";
        int need = n / 2;
        for (int i = n; i >= 1; i--) {
                ans += cur ? 'B' : 'A';
                int v = cur ? b[i] : a[i];
                need -= cur ^ 1;
                if (a[i - 1] <= v && dp_min[0][i - 1] <= need && need <= dp_max[0][i - 1]) {
                        cur = 0;
                } else {
                        assert(b[i - 1] <= v && dp_min[1][i - 1] <= need && need <= dp_max[1][i - 1]);
                        cur = 1;
                }
        }
        reverse(ans.begin(), ans.end());
        cout << ans;
}

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