Submission #383166

#	Time	Username	Problem	Language	Result	Execution time	Memory
383166		timmyfeng	Building 4 (JOI20_building4)	C++17	100 / 100	281 ms	44512 KiB

building4

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

const int N = 1000000;

int height[N][2], low[N][2], high[N][2];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    for (int i = 0; i < 2; ++i) {
        for (int j = 0; j < 2 * n; ++j) {
            cin >> height[j][i];
        }
    }

    low[0][0] = high[0][0] = 0;
    low[0][1] = high[0][1] = 1;

    for (int i = 1; i < 2 * n; ++i) {
        for (int j = 0; j < 2; ++j) {
            low[i][j] = N, high[i][j] = -N;
            for (int k = 0; k < 2; ++k) {
                if (low[i - 1][k] <= high[i - 1][k] && height[i][j] >= height[i - 1][k]) {
                    low[i][j] = min(low[i][j], low[i - 1][k] + j);
                    high[i][j] = max(high[i][j], high[i - 1][k] + j);
                }
            }
        }
    }

    int i = 2 * n - 1, j;
    if (low[2 * n - 1][0] <= n && n <= high[2 * n - 1][0]) {
        j = 0;
    } else if (low[2 * n - 1][1] <= n && n <= high[2 * n - 1][1]) {
        j = 1;
    } else {
        cout << -1 << "\n";
        exit(0);
    }

    string ans;
    while (i >= 0) {
        ans.push_back(j == 0 ? 'A' : 'B');
        n -= j, --i;
        j = low[i][1] <= n && n <= high[i][1] && height[i][1] <= height[i + 1][j];
    }
    reverse(ans.begin(), ans.end());

    cout << ans << "\n";
}

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