제출 #1276854

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1276854		duckindog	건물 4 (JOI20_building4)	C++20	100 / 100	185 ms	26032 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& i, const pii& j) { 
    if (i.first == -1) return j;
    if (j.first == -1) return i;

    return pair(min(i.first, j.first), max(i.second, j.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;

        int cur = (type ? a[i] : b[i]);

        type = -1;
        if (b[i - 1] <= cur && f[i - 1][0].first <= offset && offset <= f[i - 1][0].second) type = 0;
        if (a[i - 1] <= cur && 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: 11 / 11
• Subtask 2: 89 / 89