Submission #1324822

#TimeUsernameProblemLanguageResultExecution timeMemory
1324822chfBuilding 4 (JOI20_building4)C++20
100 / 100
265 ms127800 KiB
#include <iostream>
#include <vector>
#include <string>
#include <climits>
using namespace std;

typedef long long ll;
const ll INF = 1e18;

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

    int N;
    cin >> N;
    int M = 2 * N;
    vector<ll> A(M + 1), B(M + 1);
    for (int i = 1; i <= M; ++i) cin >> A[i];
    for (int i = 1; i <= M; ++i) cin >> B[i];

    vector<vector<ll>> aft_min(M + 2, vector<ll>(2, INF));
    vector<vector<ll>> aft_max(M + 2, vector<ll>(2, -INF));

    aft_min[M][0] = aft_max[M][0] = 0;
    aft_min[M][1] = aft_max[M][1] = 0;

    for (int i = M - 1; i >= 1; --i) {
        // 当前选A
        ll minv = INF, maxv = -INF;
        if (A[i] <= A[i + 1] && aft_min[i + 1][0] != INF) {
            minv = min(minv, 1 + aft_min[i + 1][0]);
            maxv = max(maxv, 1 + aft_max[i + 1][0]);
        }
        if (A[i] <= B[i + 1] && aft_min[i + 1][1] != INF) {
            minv = min(minv, 0 + aft_min[i + 1][1]);
            maxv = max(maxv, 0 + aft_max[i + 1][1]);
        }
        if (minv != INF) {
            aft_min[i][0] = minv;
            aft_max[i][0] = maxv;
        }

        // 当前选B
        minv = INF, maxv = -INF;
        if (B[i] <= A[i + 1] && aft_min[i + 1][0] != INF) {
            minv = min(minv, 1 + aft_min[i + 1][0]);
            maxv = max(maxv, 1 + aft_max[i + 1][0]);
        }
        if (B[i] <= B[i + 1] && aft_min[i + 1][1] != INF) {
            minv = min(minv, 0 + aft_min[i + 1][1]);
            maxv = max(maxv, 0 + aft_max[i + 1][1]);
        }
        if (minv != INF) {
            aft_min[i][1] = minv;
            aft_max[i][1] = maxv;
        }
    }

    string ans;
    int cntA = 0;
    ll last = -INF;
    for (int i = 1; i <= M; ++i) {
        bool ok = false;
        // 尝试选A
        if (A[i] >= last && aft_min[i][0] != INF) {
            ll need_min = cntA + 1 + aft_min[i][0];
            ll need_max = cntA + 1 + aft_max[i][0];
            if (need_min <= N && N <= need_max) {
                ans.push_back('A');
                cntA++;
                last = A[i];
                ok = true;
            }
        }
        if (!ok) {
            // 尝试选B
            if (B[i] >= last && aft_min[i][1] != INF) {
                ll need_min = cntA + aft_min[i][1];
                ll need_max = cntA + aft_max[i][1];
                if (need_min <= N && N <= need_max) {
                    ans.push_back('B');
                    last = B[i];
                    ok = true;
                }
            }
        }
        if (!ok) {
            cout << -1 << endl;
            return 0;
        }
    }
    cout << ans << endl;
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...