Submission #782977

#	Time	Username	Problem	Language	Result	Execution time	Memory
782977		kamelfanger83	Building 4 (JOI20_building4)	C++14	100 / 100	207 ms	25940 KiB

building4

#include <iostream>
#include <vector>
#include <limits>
#include <string>
#include <cassert>
#include <algorithm>

using namespace std;

int main(){
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    
    int n; cin >> n; n <<= 1;
    vector<pair<int, int>> ops (n);

    for (int i = 0; i < n; ++i) cin >> ops[i].first;
    for (int i = 0; i < n; ++i) cin >> ops[i].second;

    vector<pair<int, int>> lowers (n, {numeric_limits<int>::max(), numeric_limits<int>::max()}), uppers (n, {numeric_limits<int>::min(), numeric_limits<int>::min()});
    lowers[0].first = 1; lowers[0].second = 0;
    uppers[0].first = 1; uppers[0].second = 0;

    for (int i = 1; i < n; ++i) {
        if (ops[i].first >= ops[i - 1].first) {
            lowers[i].first = lowers[i - 1].first;
            uppers[i].first = uppers[i - 1].first;
        }
        if (ops[i].first >= ops[i - 1].second) {
            lowers[i].first = min(lowers[i].first, lowers[i - 1].second);
            uppers[i].first = max(uppers[i].first, uppers[i - 1].second);
        }
        if (lowers[i].first != numeric_limits<int>::max()) lowers[i].first++;
        uppers[i].first++;
        if (ops[i].second >= ops[i - 1].first) {
            lowers[i].second = lowers[i - 1].first;
            uppers[i].second = uppers[i - 1].first;
        }
        if (ops[i].second >= ops[i - 1].second) {
            lowers[i].second = min(lowers[i].second, lowers[i - 1].second);
            uppers[i].second = max(uppers[i].second, uppers[i - 1].second);
        }
    }

    auto isin = [](int l, int r, int v){
        return l <= v && v <= r;
    };

    if (!isin(lowers.back().first, uppers.back().first, n/2) && !isin(lowers.back().second, uppers.back().second, n/2)) cout << -1 << "\n";
    else {
        string ANS;
        int tbd = n/2;
        int at = numeric_limits<int>::max();
        for (int i = n - 1; i >= 0; --i) {
            if (isin(lowers[i].first, uppers[i].first, tbd) && at >= ops[i].first){
                ANS.push_back('A');
                tbd--;
                at = ops[i].first;
            }
            else if (isin(lowers[i].second, uppers[i].second, tbd) && at >= ops[i].second){
                ANS.push_back('B');
                at = ops[i].second;
            }
            else{
                assert(false);
            }
        }
        assert(tbd == 0);
        reverse(ANS.begin(), ANS.end());
        cout << ANS;
    }

    return 0;
}

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