oj.uz

Submission #626888

# Submission time Handle Problem Language Result Execution time Memory
626888 2022-08-11T23:20:32 Z chonka Swap (BOI16_swap) C++17
48 / 100
 1000 ms 7268 KB 
#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 ] ;

vector < int > sr[ 18 ][ 2 ] ;

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

static 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 ] ;
    }
    for ( int i = 0 ; i < 18 ; ++ i ) {
        sr[ i ][ 0 ].resize ( ( 1 << ( 18 - i ) ) ) ;
        sr[ i ][ 1 ].resize ( ( 1 << ( 18 - 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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4436 KB Output is correct
2 Correct 2 ms 4436 KB Output is correct
3 Correct 2 ms 4436 KB Output is correct
4 Correct 2 ms 4436 KB Output is correct
5 Correct 2 ms 4452 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4436 KB Output is correct
2 Correct 2 ms 4436 KB Output is correct
3 Correct 2 ms 4436 KB Output is correct
4 Correct 2 ms 4436 KB Output is correct
5 Correct 2 ms 4452 KB Output is correct
6 Correct 2 ms 4436 KB Output is correct
7 Correct 2 ms 4436 KB Output is correct
8 Correct 2 ms 4436 KB Output is correct
9 Correct 2 ms 4436 KB Output is correct
10 Correct 3 ms 4436 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4436 KB Output is correct
2 Correct 2 ms 4436 KB Output is correct
3 Correct 2 ms 4436 KB Output is correct
4 Correct 2 ms 4436 KB Output is correct
5 Correct 2 ms 4452 KB Output is correct
6 Correct 2 ms 4436 KB Output is correct
7 Correct 2 ms 4436 KB Output is correct
8 Correct 2 ms 4436 KB Output is correct
9 Correct 2 ms 4436 KB Output is correct
10 Correct 3 ms 4436 KB Output is correct
11 Correct 3 ms 4564 KB Output is correct
12 Correct 12 ms 4564 KB Output is correct
13 Correct 3 ms 4436 KB Output is correct
14 Correct 116 ms 4564 KB Output is correct
15 Correct 114 ms 4564 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4436 KB Output is correct
2 Correct 2 ms 4436 KB Output is correct
3 Correct 2 ms 4436 KB Output is correct
4 Correct 2 ms 4436 KB Output is correct
5 Correct 2 ms 4452 KB Output is correct
6 Correct 2 ms 4436 KB Output is correct
7 Correct 2 ms 4436 KB Output is correct
8 Correct 2 ms 4436 KB Output is correct
9 Correct 2 ms 4436 KB Output is correct
10 Correct 3 ms 4436 KB Output is correct
11 Correct 3 ms 4564 KB Output is correct
12 Correct 12 ms 4564 KB Output is correct
13 Correct 3 ms 4436 KB Output is correct
14 Correct 116 ms 4564 KB Output is correct
15 Correct 114 ms 4564 KB Output is correct
16 Correct 960 ms 7268 KB Output is correct
17 Correct 695 ms 7192 KB Output is correct
18 Execution timed out 1085 ms 6452 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #5
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4436 KB Output is correct
2 Correct 2 ms 4436 KB Output is correct
3 Correct 2 ms 4436 KB Output is correct
4 Correct 2 ms 4436 KB Output is correct
5 Correct 2 ms 4452 KB Output is correct
6 Correct 2 ms 4436 KB Output is correct
7 Correct 2 ms 4436 KB Output is correct
8 Correct 2 ms 4436 KB Output is correct
9 Correct 2 ms 4436 KB Output is correct
10 Correct 3 ms 4436 KB Output is correct
11 Correct 3 ms 4564 KB Output is correct
12 Correct 12 ms 4564 KB Output is correct
13 Correct 3 ms 4436 KB Output is correct
14 Correct 116 ms 4564 KB Output is correct
15 Correct 114 ms 4564 KB Output is correct
16 Correct 960 ms 7268 KB Output is correct
17 Correct 695 ms 7192 KB Output is correct
18 Execution timed out 1085 ms 6452 KB Time limit exceeded
19 Halted 0 ms 0 KB -