Submission #1133941

#	Time	Username	Problem	Language	Result	Execution time	Memory
1133941		OI_Account	Building 4 (JOI20_building4)	C++20	100 / 100	162 ms	25892 KiB

building4

#include <bits/stdc++.h>
using namespace std;

const int N = 1'000'000;

int n, a[2][N + 10];
pair<int, int> seg[2][N + 10];
char ans[N + 10];

void readInput() {
    cin >> n;
    for (int i = 1; i <= n + n; i++)
        cin >> a[1][i];
    for (int i = 1; i <= n + n; i++)
        cin >> a[0][i];
}

pair<int, int> merg(pair<int, int> a, pair<int, int> b) {
    if (a.first == -1)
        return b;
    if (b.first == -1)
        return a;
    return {min(a.first, b.first), max(a.second, b.second)};
}

pair<int, int> calc(int val, int mn, int mx, int id) {
    if (val < a[mn][id])
        return {-1, -1};
    if (val < a[mx][id])
        return seg[mn][id];
    return merg(seg[mn][id], seg[mx][id]);
}

pair<int, int> add(pair<int, int> a) {
    if (a.first == -1)
        return a;
    return {a.first + 1, a.second + 1};
}

void calcDP() {
    seg[1][1] = {1, 1};
    seg[0][1] = {0, 0};
    for (int i = 2; i <= n + n; i++) {
        int mn = (a[0][i - 1] <= a[1][i - 1]? 0: 1);
        int mx = 1 - mn;
        seg[1][i] = add(calc(a[1][i], mn, mx, i - 1));
        seg[0][i] = calc(a[0][i], mn, mx, i - 1);
    }
}

bool isIn(pair<int, int> seg, int x) {
    return seg.first <= x && x <= seg.second;
}

void calcAns() {
    int idx = n + n, need = n;
    int t = (isIn(seg[0][n + n], n)? 0: 1);
    while (true) {
        ans[idx] = (t == 0? 'B': 'A');
        need -= t;
        if (idx == 1)
            break;
        if (isIn(seg[0][idx - 1], need) && a[0][idx - 1] <= a[t][idx])
            t = 0;
        else
            t = 1;
        idx--;
    }
}

void writeOutput() {
    if (isIn(seg[0][n + n], n) || isIn(seg[1][n + n], n)) {
        calcAns();
        for (int i = 1; i <= n + n; i++)
            cout << ans[i];
    }
    else
        cout << -1;
    cout.flush();
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    readInput();
    calcDP();
    writeOutput();
    return 0;
}

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