Submission #1276845

#	Time	Username	Problem	Language	Result	Execution time	Memory
1276845		duckindog	Building 4 (JOI20_building4)	C++20	0 / 100	1 ms	340 KiB

building4

#include <bits/stdc++.h>

using namespace std;

const int N = 1'000'000 + 10;
int n;
int a[N], b[N];

using pii = pair<int, int>;
pii f[N][2];
pii merge(const pii& lt, const pii& rt) { 
    if (lt.first == -1) return rt;
    if (rt.first == -1) return lt;

    return pair(min(lt.first, rt.first), max(lt.second, rt.second));
}

int32_t main() { 
    cin.tie(0)->sync_with_stdio(0);

    cin >> n;
    for (int i = 1; i <= 2 * n; ++i) cin >> a[i];
    for (int i = 1; i <= 2 * n; ++i) cin >> b[i];

    for (int i = 1; i <= 2 * n; ++i) { 
        { // f[i][1]
            auto& ret = f[i][1];
            ret = {-1, -1};
            if (b[i - 1] < a[i]) ret = merge(ret, f[i - 1][0]);
            if (a[i - 1] < a[i]) ret = merge(ret, f[i - 1][1]);
        }

        { // f[i][0]
            auto& ret = f[i][0];
            ret = {-1, -1};
            if (b[i - 1] < b[i]) ret = merge(ret, f[i - 1][0]);
            if (a[i - 1] < b[i]) ret = merge(ret, f[i - 1][1]);

            if (ret.first != -1) {
                ret.first += 1;
                ret.second += 1;
            }
        }
    }
    
    int type = -1;
    if (f[2 * n][0].first <= n && n <= f[2 * n][0].second) type = 0;
    if (f[2 * n][1].first <= n && n <= f[2 * n][1].second) type = 1;

    if (type == -1) { 
        cout << -1 << "\n";
        return 0;
    }

    int offset = n;

    string answer;
    for (int i = 2 * n; i >= 1; --i) { 
        answer += (type ? 'A' : 'B');

        offset -= !type;

        type = -1;
        if (f[i - 1][0].first <= offset && offset <= f[i - 1][0].second) type = 0;
        if (f[i - 1][1].first <= offset && offset <= f[i - 1][1].second) type = 1;
        assert(type != -1);
    }
    reverse(answer.begin(), answer.end());

    cout << answer << "\n";
}

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