제출 #905208

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
905208		DAleksa	Building 4 (JOI20_building4)	C++17	100 / 100	268 ms	45568 KiB

building4

#include <bits/stdc++.h>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    n *= 2;
    vector<int> a(n), b(n);
    for(int i = 0; i < n; i++) cin >> a[i];
    for(int i = 0; i < n; i++) cin >> b[i];
    vector<int> mna(n, 1e9), mnb(n, 1e9), mxa(n, -1e9), mxb(n, -1e9);
    mna[0] = mxa[0] = 1;
    mnb[0] = mxb[0] = -1;
    for(int i = 1; i < n; i++) {
        if(a[i] >= a[i - 1]) {
            mxa[i] = max(mxa[i], mxa[i - 1]);
            mna[i] = min(mna[i], mna[i - 1]);
        }
        if(a[i] >= b[i - 1]) {
            mxa[i] = max(mxa[i], mxb[i - 1]);
            mna[i] = min(mna[i], mnb[i - 1]);
        }
        if(b[i] >= a[i - 1]) {
            mxb[i] = max(mxb[i], mxa[i - 1]);
            mnb[i] = min(mnb[i], mna[i - 1]);
        }
        if(b[i] >= b[i - 1]) {
            mxb[i] = max(mxb[i], mxb[i - 1]);
            mnb[i] = min(mnb[i], mnb[i - 1]);
        }
        mxa[i]++;
        mna[i]++;
        mxb[i]--;
        mnb[i]--;
    }
    if(min(mna[n - 1], mnb[n - 1]) > 0 || max(mxa[n - 1], mxb[n - 1]) < 0) {
        cout << -1;
        return 0;
    }
    string s;
    bool oka = true, okb = true;
    int border = 0;
    for(int i = n - 1; i >= 0; i--) {
        if(oka) {
            if(mna[i] <= border && border <= mxa[i]) {
                s += 'A';
                border--;
                oka = (a[i] >= a[i - 1]);
                okb = (a[i] >= b[i - 1]);
                continue;
            }
        }
        if(okb) {
            if(mnb[i] <= border && border <= mxb[i]) {
                s += 'B';
                border++;
                oka = (b[i] >= a[i - 1]);
                okb = (b[i] >= b[i - 1]);
            }
        }
    }
    reverse(s.begin(), s.end());
    cout << s;
    return 0;
}

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