Submission #1225390

#	Time	Username	Problem	Language	Result	Execution time	Memory
1225390		Double_Slash	Building 4 (JOI20_building4)	C++20	0 / 100	0 ms	324 KiB

building4

#include <bits/stdc++.h>

using namespace std;

int main() {
    int n;
    cin >> n;
    int a[n <<= 1][2];
    for (int i = 0; i < n; ++i) cin >> a[i][0];
    for (int i = 0; i < n; ++i) cin >> a[i][1];
    auto dp = [&] (int a[][2]) {
        auto dp = new int[n][2]{{1, -1}};
        for (int i = 0; ++i < n;) {
            for (int x = 2; x--;) dp[i][x] = max(
                a[i][x] > a[i - 1][0] ? dp[i - 1][0] : -n,
                a[i][x] > a[i - 1][1] ? dp[i - 1][1] : -n) + not x - x;
        }
        for (int i = n; i--;) swap(a[i][0], a[i][1]);
        return dp;
    };
    auto top = dp(a), bot = dp(a);
    if (min(max(top[n - 1][0], top[n - 1][1]), max(bot[n - 1][0], bot[n - 1][1])) < 0) {
        cout << "-1\n";
        return 0;
    }
    bool ans[n];
    for (int i = n, sum = 0; i--;) {
        if (i) {
            ans[i] = (i == n - 1 or a[i][1] <= a[i + 1][ans[i + 1]]) and top[i][1] + sum >= 0;
            sum += not ans[i] - ans[i];
        } else ans[i] = sum > 0;
    }
    for (bool b: ans) cout << (char) ('A' + b);
}

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