Submission #626885

#	Time	Username	Problem	Language	Result	Execution time	Memory
626885		chonka	Swap (BOI16_swap)	C++17	48 / 100	1083 ms	3972 KiB

swap

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

const int MAXN = 2e5 + 7 ;

int n ;
int a[ MAXN ] , f[ MAXN ] ;
int b[ MAXN ] ;

int sr[ 18 ][ 2 ][ MAXN ] ;

int rem[ 18 ][ MAXN ] ;

void fill ( int x , int lvl ) {
    rem[ lvl ][ x ] = a[ x ] ;
    if ( 2 * x <= n ) { fill ( 2 * x , lvl ) ; }
    if ( 2 * x + 1 <= n ) { fill ( 2 * x + 1 , lvl ) ; }
}
void revert ( int x , int lvl ) {
    a[ x ] = rem[ lvl ][ x ] ;
    if ( 2 * x <= n ) { revert ( 2 * x , lvl ) ; }
    if ( 2 * x + 1 <= n ) { revert ( 2 * x + 1 , lvl ) ; }
}

void fill_ord ( int x , int lvl , int id ) {
    int tp = 0 ;
    sr[ lvl ][ id ][ tp ++ ] = a[ x ] ;
    for ( int aux = 1 ; aux < 20 ; ++ aux ) {
        x *= 2 ;
        for ( int j = 0 ; j < ( 1 << aux ) ; ++ j ) {
            if ( x + j > n ) { return ; }
            sr[ lvl ][ id ][ tp ++ ] = a[ x + j ] ;
        }
    }
}

void rec ( int wh , int lvl ) {
    if ( 2 * wh > n ) {
        f[ wh ] = 0 ;
        return ;
    }
    if ( 2 * wh + 1 <= n ) {
        if ( a[ wh ] < a[ 2 * wh ] && a[ wh ] < a[ 2 * wh + 1 ] ) {
            f[ wh ] = 0 ;
        }
        else if ( a[ 2 * wh ] < a[ wh ] && a[ 2 * wh ] < a[ 2 * wh + 1 ] ) {
            f[ wh ] = 1 ;
            swap ( a[ wh ] , a[ 2 * wh ] ) ;
        }
        else {
            fill ( wh , lvl ) ;
            swap ( a[ wh ] , a[ 2 * wh + 1 ] ) ;
            if ( 2 * wh <= n ) { rec ( 2 * wh , lvl + 1 ) ; }
            if ( 2 * wh + 1 <= n ) { rec ( 2 * wh + 1 , lvl + 1 ) ; }
            fill_ord ( wh , lvl , 0 ) ;
            revert ( wh , lvl ) ;
            swap ( a[ wh ] , a[ 2 * wh ] ) ;
            swap ( a[ wh ] , a[ 2 * wh + 1 ] ) ;
            if ( 2 * wh <= n ) { rec ( 2 * wh , lvl + 1 ) ; }
            if ( 2 * wh + 1 <= n ) { rec ( 2 * wh + 1 , lvl + 1 ) ; }
            fill_ord ( wh , lvl , 1 ) ;
            revert ( wh , lvl ) ;
            bool sw = false ;
            for ( int i = 1 ; i <= n ; ++ i ) {
                if ( sr[ lvl ][ 0 ][ i ] != sr[ lvl ][ 1 ][ i ] ) {
                    if ( sr[ lvl ][ 0 ][ i ] < sr[ lvl ][ 1 ][ i ] ) {
                        sw = true ;
                    }
                    break ;
                }
            }
            if ( sw == false ) {
                f[ wh ] = 3 ;
                swap ( a[ wh ] , a[ 2 * wh ] ) ;
                swap ( a[ wh ] , a[ 2 * wh + 1 ] ) ;
            }
            else {
                f[ wh ] = 2 ;
                swap ( a[ wh ] , a[ 2 * wh + 1 ] ) ;
            }
        }
    }
    else {
        if ( a[ wh ] < a[ 2 * wh ] ) {
            f[ wh ] = 0 ;
        }
        else {
            f[ wh ] = 1 ;
            swap ( a[ wh ] , a[ 2 * wh ] ) ;
        }
        return ;
    }
    if ( 2 * wh <= n ) { rec ( 2 * wh , lvl + 1 ) ; }
    if ( 2 * wh + 1 <= n ) { rec ( 2 * wh + 1 , lvl + 1 ) ; }
}

void solve ( ) {
    cin >> n ;
    for ( int i = 1 ; i <= n ; ++ i ) {
        cin >> a[ i ] ;
    }
    rec ( 1 , 0 ) ;
    for ( int i = 1 ; i <= n ; ++ i ) {
        cout << a[ i ] << " " ;
    }
    cout << "\n" ;
}

int main ( ) {
    ios_base :: sync_with_stdio ( false ) ;
    cin.tie ( NULL ) ;
    int t = 1 ; // cin >> t ; 
    while ( t -- ) { solve ( ) ; }
    return 0 ;
}

• Subtask 1: 10 / 10
• Subtask 2: 11 / 11
• Subtask 3: 27 / 27
• Subtask 4: 0 / 20
• Subtask 5: 0 / 32