Submission #829550

#	Time	Username	Problem	Language	Result	Execution time	Memory
829550		LucaIlie	Building 4 (JOI20_building4)	C++17	100 / 100	609 ms	45532 KiB

building4

#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;
}

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