제출 #1137217

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1137217		RaresFelix	Building 4 (JOI20_building4)	C++20	100 / 100	210 ms	151284 KiB

building4

#include <bits/stdc++.h>

using namespace std;

//#define int ll

using ll = long long;
using vi = vector<int>;
using ii = pair<int, int>;
using vll = vector<ll>;

const int INF = 1e9;

int main() {
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    int n;
    cin >> n;
    vi A(2 * n), B(2 * n);
    for(int i = 0; i < 2 * n; ++i) cin >> A[i];
    for(int i = 0; i < 2 * n; ++i) cin >> B[i];

    ///DP[poz][0 / 1] -> range cntB
    vector<array<ii, 2> > DP(2 * n + 1, array<ii, 2>{ii{INF, -INF}, ii{INF, -INF}});
    vector<array<ii, 2> > Orig(2 * n + 1);

    DP[0][0] = {0, 0}; DP[0][1] = {1, 1};
    for(int poz = 0; poz + 1 < 2 * n; ++poz) {
        for(int t1 = 0; t1 < 2; ++t1) {
            for(int t2 = 0; t2 < 2; ++t2) {
                int v1 = (t1 ? B[poz] : A[poz]), v2 = t2 ? B[poz + 1] : A[poz + 1];
                auto [mi1, ma1] = DP[poz][t1];
                auto &[mi2, ma2] = DP[poz + 1][t2];
                auto &[orig_mi, orig_ma] = Orig[poz + 1][t2];
                if(v1 <= v2) {
                    if(mi1 + t2 < mi2) {
                        mi2 = mi1 + t2;
                        orig_mi = t1;
                    }
                    if(ma1 + t2 > ma2) {
                        ma2 = ma1 + t2;
                        orig_ma = t1;
                    }
                }
            }
        }
    }
    string re;
    function<void(int, int, int)> reconstruct = [&](int k, int ramas, int tip) {
        ///sunt la poz k, unde am pus ceva de tipul tip
        int v2 = tip ? B[k] : A[k];
        if(tip) re += 'B'; else re += 'A';
        if(!k) return;
        ramas -= tip;
        for(int t1 = 0; t1 < 2; ++t1) {
            int v1 = t1 ? B[k - 1] : A[k - 1];
            if(v1 <= v2) {
                auto [mi1, ma1] = DP[k - 1][t1];
                if(mi1 <= ramas && ramas <= ma1) {
                    reconstruct(k - 1, ramas, t1);
                    break;
                }
            }
        }
    };
    bool ok = false;
    if(DP[2 * n - 1][0].first <= n && n <= DP[2 * n - 1][0].second) reconstruct(2 * n - 1, n, 0);
    else if(DP[2 * n - 1][1].first <= n && n <= DP[2 * n - 1][1].second) reconstruct(2 * n - 1, n, 1);
    reverse(re.begin(), re.end());
    if(!re.empty()) cout << re << "\n";
    else cout << "-1\n";
    return 0;
}

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