제출 #249822

#제출 시각아이디문제언어결과실행 시간메모리
249822Tc14건물 4 (JOI20_building4)C++17
100 / 100
351 ms28152 KiB
//#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define ve vector
typedef long long ll;
typedef pair<int, int> pii;
const int INF = 1e9 + 10;

int main() {

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, r, v;
    ve<int> A, B;
    ve<pii> Ap, Bp;
    ve<bool> Sol;

    cin >> n;
    A = ve<int>(2 * n);
    B = ve<int>(2 * n);
    Ap = ve<pii>(2 * n, { INF, -INF });
    Bp = ve<pii>(2 * n, { INF, -INF });
    Sol = ve<bool>(2 * n);

    for (int i = 0; i < 2 * n; i++) cin >> A[i];
    for (int i = 0; i < 2 * n; i++) cin >> B[i];

    Ap[0] = {1, 1};
    Bp[0] = {0, 0};

    for (int i = 1; i < 2 * n; i++) {

        if (A[i - 1] <= A[i]) {
            Ap[i] = {min(Ap[i].first, Ap[i - 1].first), max(Ap[i].second, Ap[i - 1].second)};
        }
        if (B[i - 1] <= A[i]) {
            Ap[i] = {min(Ap[i].first, Bp[i - 1].first), max(Ap[i].second, Bp[i - 1].second)};
        }

        if (A[i - 1] <= B[i]) {
            Bp[i] = {min(Bp[i].first, Ap[i - 1].first), max(Bp[i].second, Ap[i - 1].second)};
        }
        if (B[i - 1] <= B[i]) {
            Bp[i] = {min(Bp[i].first, Bp[i - 1].first), max(Bp[i].second, Bp[i - 1].second)};
        }

        if (Ap[i].first != INF) {
            Ap[i].first++;
            Ap[i].second++;
        }
    }

    if (Ap[2 * n - 1].first <= n && n <= Ap[2 * n - 1].second) r = 0;
    else if (Bp[2 * n - 1].first <= n && n <= Bp[2 * n - 1].second) r = 1;
    else r = -1;

    if (r == -1) cout << -1 << endl;
    else {
        Sol[2 * n - 1] = r;
        v = n;
        for (int i = 2 * n - 2; i >= 0; i--) {
            if (r == 0) {
                v--;
                if (A[i] <= A[i + 1] && Ap[i].first <= v && v <= Ap[i].second) r = 0;
                else r = 1;
            }
            else {
                if (A[i] <= B[i + 1] && Ap[i].first <= v && v <= Ap[i].second) r = 0;
                else r = 1;
            }
            Sol[i] = r;
        }

        for (int i = 0; i < 2 * n; i++) {
            if (Sol[i] == 0) cout << "A";
            else cout << "B";
        }
        cout << endl;
    }

    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...