제출 #1068986

#제출 시각아이디문제언어결과실행 시간메모리
1068986_8_8_건물 4 (JOI20_building4)C++17
100 / 100
189 ms45520 KiB
#include <bits/stdc++.h>

using namespace std;
    
typedef long long ll;
const int  N = 1e6 + 12, MOD = (int)1e9 + 7;

int n,a[N][2];
int mx[N][2],mn[N][2];
bool in(int l,int r,int x) {
    return (l <= x && x <= r);
}
void test() {
    cin >> n;
    for(int i = 1; i <= n + n; i++) {
        cin >> a[i][1];
    }
    for(int i = 1; i <= n + n; i++) {
        cin >> a[i][0];
    }
    for(int i = 1; i <= n + n; i++) {
        for(int k = 0;k < 2;k++) {
            mn[i][k] = 1e9;
            mx[i][k] = -1e9;
            for(int t = 0;t < 2;t++) {
                if(a[i][k] >= a[i - 1][t]) {
                    mx[i][k] = max(mx[i - 1][t] + k,mx[i][k]);
                    mn[i][k] = min(mn[i][k],k + mn[i - 1][t]);
                }
            }
        }
    }
    if(!in(mn[n + n][0],mx[n + n][0],n) && !in(mn[n + n][1],mx[n + n][1],n)) {
        cout << -1 << '\n';
        return;
    }
    int cur = n,lst = 1e9 + 1;
    vector<char> res;
    for(int i = n + n;i >= 1;i--) {
        if(cur && a[i][1] <= lst && in(mn[i][1],mx[i][1],cur)) {
            cur--;
            res.push_back('A');
            lst = a[i][1];
        } else {
            lst = a[i][0];
            res.push_back('B');
        }
    }
    reverse(res.begin(),res.end());
    for(auto x:res) {
        cout << x;
    }
    cout << '\n';
}
int main() {
    ios_base::sync_with_stdio(false);cin.tie(0);
    int t = 1; 
    // cin >> t;
    while(t--) {
        test();
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...