제출 #829550

#제출 시각아이디문제언어결과실행 시간메모리
829550LucaIlieBuilding 4 (JOI20_building4)C++17
100 / 100
609 ms45532 KiB
#include <bits/stdc++.h>

using namespace std;

struct interval {
    int l, r;

    interval operator + ( interval x ) const {
        return { min( l, x.l ), max( r, x.r ) };
    }

    interval operator + ( int x ) const {
        return { l + x, r + x };
    }
};

const int MAX_N = 5e5;
int a[2 * MAX_N + 1], b[2 * MAX_N + 1];
interval dp[2 * MAX_N + 1][2];

int main() {
    int n;

    cin >> n;
    for ( int i = 1; i <= 2 * n; i++ )
        cin >> a[i];
    for ( int i = 1; i <= 2 * n; i++ )
        cin >> b[i];

    dp[0][0] = dp[0][1] = { 0, 0 };
    for ( int i = 1; i <= 2 * n; i++ ) {
        dp[i][0] = { 2 * i, 0 };
        if ( a[i] >= a[i - 1] )
            dp[i][0] = dp[i][0] + (dp[i - 1][0] + 1);
        if ( a[i] >= b[i - 1] )
            dp[i][0] = dp[i][0] + (dp[i - 1][1] + 1);

        dp[i][1] = { 2 * i, 0 };
        if ( b[i] >= a[i - 1] )
            dp[i][1] = dp[i][1] + dp[i - 1][0];
        if ( b[i] >= b[i - 1] )
            dp[i][1] = dp[i][1] + dp[i - 1][1];
    }

    if ( !((dp[2 * n][0].l <= n && n <= dp[2 * n][0].r) || (dp[2 * n][1].l <= n && n <= dp[2 * n][1].r)) ) {
        cout << -1;
        return 0;
    }

    vector<char> sol;
    int j = n, lastt = 1e9;
    for ( int i = 2 * n; i >= 1; i-- ) {
        if ( dp[i][0].l <= j && j <= dp[i][0].r && a[i] <= lastt ) {
            sol.push_back( 'A' );
            lastt = a[i];
            j--;
        } else {
            sol.push_back( 'B' );
            lastt = b[i];
        }
    }


    reverse( sol.begin(), sol.end() );
    for ( char c: sol )
        cout << c;

    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...