Submission #211618

#	Time	Username	Problem	Language	Result	Execution time	Memory
211618		diegogrc	Building 4 (JOI20_building4)	C++17	100 / 100	816 ms	95688 KiB

building4

//  Copyright © 2020 Diego Garcia Rodriguez del Campo. All rights reserved.
#include<bits/stdc++.h>
#define INF 1e9
#define MAX 1000005
#define optimiza_io cin.tie(0); ios_base::sync_with_stdio(0);
using namespace std;
typedef long long i64;

int N;
int a[MAX][2];
int dpmn[MAX][2];
int dpmx[MAX][2];

struct node {
    int vl, i, j;
    bool operator < ( const node & a ) const {
        if( vl == a.vl )
            return i > a.i;
        return vl > a.vl;
    }
};

vector < node > q;

void solve( int i , int j , int r ) {
    cout << ( j ? 'B' : 'A' );
    if( i == N )
        return;
    // Ir a la A
    if( a[i][j] <= a[i + 1][0] && 
        dpmn[i + 1][0] <= r &&
        dpmx[i + 1][0] >= r )
        solve( i + 1 , 0 , r - 1 );
    else
        solve( i + 1 , 1 , r );
    
}

int main()
{
    optimiza_io
    cin >> N;
    N *= 2;
    for( int j = 0; j < 2; j ++ )
        for( int i = 1; i <= N; i ++ ) { 
            cin >> a[i][j];
            dpmx[i][j] = -INF;
            dpmn[i][j] = INF;
            q.push_back( { a[i][j] , i , j } );
        }
    
    sort( q.begin() , q.end() );
    for( auto x : q ) {
        if( x.i == N ) {
            dpmn[x.i][x.j] = dpmx[x.i][x.j] = ! x.j;
            continue;
        }
        
        dpmn[x.i][x.j] = min( dpmn[x.i + 1][0] , dpmn[x.i + 1][1] ) + ( ! x.j );
        dpmx[x.i][x.j] = max( dpmx[x.i + 1][0] , dpmx[x.i + 1][1] ) + ( ! x.j );
    }
    
    /* for( int j = 0; j < 2; j ++ )
        for( int i = 1; i <= N; i ++ )
            cout << dpmn[i][j] << " \n"[i == N];
    
    cout << "\n\n";
            
    for( int j = 0; j < 2; j ++ )
        for( int i = 1; i <= N; i ++ )
            cout << dpmx[i][j] << " \n"[i == N];
    */
            

    
    if( dpmn[1][0] <= N/2 && dpmx[1][0] >= N/2 )
        solve( 1 , 0 , N/2 - 1 );
    else if( dpmn[1][1] <= N/2 && dpmx[1][1] >= N/2 )
        solve( 1 , 1 , N/2 );
    else 
        cout << "-1\n";
    return 0;
}

// CHECAR LIMITES 

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