제출 #1298990

#제출 시각아이디문제언어결과실행 시간메모리
1298990chithanhnguyen건물 4 (JOI20_building4)C++20
100 / 100
192 ms56356 KiB
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define ld long double
#define pii pair<int, int>
#define fi first
#define se second
#define __builtin_popcount __builtin_popcountll
#define all(x) (x).begin(), (x).end()
#define BIT(x, i) (((x) >> (i)) & 1)
#define MASK(x) ((1ll << (x)))

#define debug(a, l, r) for (int _i = (l); _i <= (r); ++_i) cout << (a)[_i] << ' '; cout << '\n';

const int MAXN = 1e6 + 6;
const int INF  = 1e18 + 7;

int n, a[MAXN][2], dpmx[MAXN][2], dpmi[MAXN][2];

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

void solve() {
    dpmx[1][0] = dpmi[1][0] = 1;
    dpmx[1][1] = dpmi[1][1] = -1;

    for (int i = 2; i <= n; ++i) {
        for (int cur = 0; cur < 2; ++cur) {
            dpmx[i][cur] = -INF; dpmi[i][cur] = INF;
            for (int pre = 0; pre < 2; ++pre) {
                int weight = (cur == 0 ? 1 : -1);
                if (a[i - 1][pre] <= a[i][cur]) {
                    if (dpmx[i - 1][pre] != -INF) dpmx[i][cur] = max(dpmx[i][cur], dpmx[i - 1][pre] + weight);
                    if (dpmi[i - 1][pre] != INF) dpmi[i][cur] = min(dpmi[i][cur], dpmi[i - 1][pre] + weight);
                }
            }
        }

        // cout << dpmi[i][0] << ' ' << dpmx[i][0] << '\n';
        // cout << dpmi[i][1] << ' ' << dpmx[i][1] << '\n';
        // cout << '\n';
    }

    // Trace
    int en = -1;
    if (dpmi[n][0] <= 0 && 0 <= dpmx[n][0]) en = 0;
    else if (dpmi[n][1] <= 0 && 0 <= dpmx[n][1]) en = 1;
    if (en == -1) {
        cout << -1;
        return;
    }

    int sum = 0, pos = n, state = en;
    vector<int> res;
    while (pos >= 1) {
        res.push_back(state);
        int weight = (state == 0 ? 1 : -1);
        sum -= weight;
        --pos;
        if (a[pos][0] <= a[pos+1][state] && dpmi[pos][0] <= sum && sum <= dpmx[pos][0]) state = 0;
        else if (a[pos][1] <= a[pos+1][state] && dpmi[pos][1] <= sum && sum <= dpmx[pos][1]) state = 1;
    }

    reverse(all(res));
    for (int u : res) cout << (u ? 'B' : 'A');
}

signed main() {
    #ifdef NCTHANH
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif
    ios_base::sync_with_stdio(0);
    cin.tie(nullptr); cout.tie(nullptr);

    init();
    solve();

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