Submission #1365395

#TimeUsernameProblemLanguageResultExecution timeMemory
1365395nguyenkhangninh99건물 4 (JOI20_building4)C++20
100 / 100
151 ms56348 KiB
#include<bits/stdc++.h>
using namespace std;

#define int long long
const int maxn = 1e6 + 6;
int a[maxn][2], dpmx[maxn][2], dpmi[maxn][2], w[2];

void solve() {
    int n; 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];
    dpmx[1][0] = dpmi[1][0] = w[0] = 1;
    dpmx[1][1] = dpmi[1][1] = w[1] = -1;

    for(int i = 2; i <= n; i++){
        for(int cur = 0; cur <= 1; cur++){
            dpmx[i][cur] = -1e18; 
            dpmi[i][cur] = 1e18;
            for(int pre = 0; pre <= 1; pre++){
                if(a[i - 1][pre] <= a[i][cur]){
                    dpmx[i][cur] = max(dpmx[i][cur], dpmx[i - 1][pre] + w[cur]);
                    dpmi[i][cur] = min(dpmi[i][cur], dpmi[i - 1][pre] + w[cur]);
                }
            }
        }
    }

    int sum = 0, pos = n, state;
    if(dpmi[n][0] <= 0 && 0 <= dpmx[n][0]) state = 0;
    else if(dpmi[n][1] <= 0 && 0 <= dpmx[n][1]) state = 1;
    else{
        cout << -1;
        return;
    }

    vector<int> res;
    while(pos >= 1){
        res.push_back(state);
        sum -= w[state];
        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(res.begin(), res.end());
    for(int u : res) cout << (u ? 'B' : 'A');
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    solve();
}
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...