Submission #582736

#	Time	Username	Problem	Language	Result	Execution time	Memory
582736		elkernos	Building 4 (JOI20_building4)	C++17	100 / 100	305 ms	84280 KiB

building4

#include <bits/stdc++.h>

using namespace std;

int main()
{
    cin.tie(nullptr)->sync_with_stdio(0);
    int n;
    cin >> n;
    vector<int> a(2 * n), b(2 * n);
    for(int &i : a) {
        cin >> i;
    }
    for(int &i : b) {
        cin >> i;
    }
    const int oo = 1e9;
    vector<vector<pair<int, int>>> dp(2 * n, vector<pair<int, int>>(2, {oo, -oo}));
    dp[0][0] = {1, 1};
    dp[0][1] = {0, 0};
    auto merge = [&](pair<int, int> &one, pair<int, int> &two, int offset) {
        one = {min(one.first, two.first + offset), max(one.second, two.second + offset)};
    };
    for(int i = 0; i < 2 * n - 1; i++) {
        if(a[i] <= a[i + 1]) merge(dp[i + 1][0], dp[i][0], 1);
        if(a[i] <= b[i + 1]) merge(dp[i + 1][1], dp[i][0], 0);
        if(b[i] <= a[i + 1]) merge(dp[i + 1][0], dp[i][1], 1);
        if(b[i] <= b[i + 1]) merge(dp[i + 1][1], dp[i][1], 0);
    }
    int used = n, nxt = oo;
    string ans(2 * n, '?');
    for(int i = 2 * n - 1; i >= 0; i--) {
        if(dp[i][0].first <= used && used <= dp[i][0].second && a[i] <= nxt) {
            ans[i] = 'A';
            used--;
            nxt = a[i];
        }
        else if(dp[i][1].first <= used && used <= dp[i][1].second && b[i] <= nxt) {
            ans[i] = 'B';
            nxt = b[i];
        }
        else {
            cout << "-1" << '\n';
            exit(0);
        }
    }
    cout << ans << '\n';
}

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