Submission #249822

#	Time	Username	Problem	Language	Result	Execution time	Memory
249822		Tc14	Building 4 (JOI20_building4)	C++17	100 / 100	351 ms	28152 KiB

building4

//#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;
}

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