제출 #542709

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
542709		chonka	건물 4 (JOI20_building4)	C++98	100 / 100	266 ms	60012 KiB

building4

#include<bits/stdc++.h>
using namespace std ;
typedef long long ll ;

#define MAXN 1000007
int n ;
int a[ MAXN ][ 3 ] ;
int ans[ MAXN ] ;
pair < int , int > dp[ MAXN ][ 3 ] ;

void input ( ) {
    cin >> n ;
    n *= 2 ;
    for ( int i = 1 ; i <= n ; ++ i ) {
        cin >> a[ i ][ 1 ] ;
    }
    for ( int i = 1 ; i <= n ; ++ i ) {
        cin >> a[ i ][ 2 ] ;
    }
}

void solve ( ) {
    for ( int i = 1 ; i <= n ; ++ i ) {
        for ( int j = 1 ; j <= 2 ; ++ j ) {
            dp[ i ][ j ] = { MAXN , -MAXN } ;
        }
    }
    dp[ 1 ][ 1 ] = { 1 , 1 } ;
    dp[ 1 ][ 2 ] = { 0 , 0 } ;
    for ( int i = 2 ; i <= n ; ++ i ) {
        for ( int j = 1 ; j <= 2 ; ++ j ) {
            for ( int t = 1 ; t <= 2 ; ++ t ) {
                if ( a[ i ][ j ] >= a[ i - 1 ][ t ] ) {
                    dp[ i ][ j ].first = min ( dp[ i ][ j ].first , dp[ i - 1 ][ t ].first + ( j == 1 ) ) ;
                    dp[ i ][ j ].second = max ( dp[ i ][ j ].second , dp[ i - 1 ][ t ].second + ( j == 1 ) ) ;
                }
            }
        }
    }
    int sr = ( n / 2 ) ;
    int x = n , y = -1 ;
    if ( dp[ n ][ 1 ].first <= sr && sr <= dp[ n ][ 1 ].second ) { y = 1 ; }
    if ( dp[ n ][ 2 ].first <= sr && sr <= dp[ n ][ 2 ].second ) { y = 2 ; }
    if ( y == -1 ) {
        cout << "-1\n" ;
        return ;
    }
    ans[ x ] = y ;
    while ( x > 1 ) {
        sr -= ( y == 1 ) ;
        if ( a[ x - 1 ][ 1 ] <= a[ x ][ y ] && dp[ x - 1 ][ 1 ].first <= sr && sr <= dp[ x - 1 ][ 1 ].second ) {
            y = 1 ;
        }
        else {
            y = 2 ;
        }
        -- x ;
        ans[ x ] = y ;
    }
    for ( int i = 1 ; i <= n ; ++ i ) {
        if ( ans[ i ] == 1 ) { cout << "A" ; }
        else { cout << "B" ; }
    }
    cout << "\n" ;
}

int main ( ) {
    //freopen ( "dictionary.in" , "r" , stdin ) ;
    ios_base :: sync_with_stdio ( false ) ;
    cin.tie ( NULL ) ;
    int t = 1 ;
    // cin >> t ;
    while ( t -- ) {
        input ( ) ;
        solve ( ) ;
    }
    return 0 ;
}

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