제출 #542575

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

building4

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

#define MAXN 1000007
int n ;
int a[ MAXN ] , b[ MAXN ] ;

int forced[ MAXN ] ;

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

void solve ( ) {
    for ( int i = 1 ; i < n ; ++ i ) {
        if ( min ( a[ i ] , b[ i ] ) > max ( a[ i + 1 ] , b[ i + 1 ] ) ) {
            cout << "-1\n" ;
            return ;
        }
        if ( a[ i ] > a[ i + 1 ] && a[ i ] > b[ i + 1 ] ) {
            if ( forced[ i ] == 1 ) {
                cout << "-1\n" ;
                return ;
            }
            forced[ i ] = 2 ;
        }
        if ( b[ i ] > a[ i + 1 ] && b[ i ] > b[ i + 1 ] ) {
            if ( forced[ i ] == 2 ) {
                cout << "-1\n" ;
                return ;
            }
            forced[ i ] = 1 ;
        }
        if ( a[ i + 1 ] < a[ i ] && a[ i + 1 ] < b[ i ] ) {
            forced[ i + 1 ] = 2 ;
        }
        if ( b[ i + 1 ] < a[ i ] && b[ i + 1 ] < b[ i ] ) {
            forced[ i + 1 ] = 1 ; 
        }
    }
    int cnt1 , cnt2 ;
    cnt1 = cnt2 = 0 ;
    for ( int i = 1 ; i <= n ; ++ i ) {
        if ( forced[ i ] == 1 ) { ++ cnt1 ; }
        if ( forced[ i ] == 2 ) { ++ cnt2 ; }
    }
    if ( cnt1 > n / 2 || cnt2 > n / 2 ) {
        cout<< "-1\n" ;
        return ;
    }
    vector < pair < ll , int > > v ;
    for ( int i = 1 ; i <= n ; ++ i ) {
        if ( forced[ i ] == 0 ) {
            ++ cnt1 , forced[ i ] = 1 ;
            v.push_back ( { a[ i ] - b[ i ] , i } ) ;
        }
    }
    sort ( v.begin ( ) , v.end ( ) ) ;
    int sz = v.size ( ) ;
    for ( int i = 0 ; i < sz ; ++ i ) {
        if ( cnt1 == n / 2 ) { break ; }
        forced[ v[ i ].second ] = 2 ;
        -- cnt1 ;
    }
    for ( int i = 1 ; i <= n ; ++ i ) {
        if ( forced[ 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: 0 / 11
• Subtask 2: 0 / 89