oj.uz

Submission #626893

# Submission time Handle Problem Language Result Execution time Memory
626893 2022-08-11T23:29:35 Z chonka Swap (BOI16_swap) C++17
48 / 100
 1000 ms 7288 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 ) ; }
}

static void fill_ord ( int x , int lvl , int id ) {
    int tp = 0 ;
    sr[ lvl ][ id ][ tp ++ ] = a[ x ] ;
    a[ x ] = rem[ lvl ][ x ] ;
    int ori = 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 ] ;
            a[ x + j ] = rem[ lvl ][ x + j ] ;
        }
    }
}

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

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

            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 ;
                fill_back ( wh , lvl , 1 ) ;
            }
            else {
                f[ wh ] = 2 ;
                fill_back ( wh , lvl , 0 ) ;
            }
            return ;
        }
    }
    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 ;
}

Compilation message

swap.cpp: In function 'void fill_ord(int, int, int)':
swap.cpp:25:9: warning: unused variable 'ori' [-Wunused-variable]
   25 |     int ori = x ;
      |         ^~~
swap.cpp: In function 'void fill_back(int, int, int)':
swap.cpp:39:9: warning: unused variable 'ori' [-Wunused-variable]
   39 |     int ori = x ;
      |         ^~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 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 4436 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 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 4436 KB Output is correct
6 Correct 2 ms 4448 KB Output is correct
7 Correct 2 ms 4436 KB Output is correct
8 Correct 3 ms 4436 KB Output is correct
9 Correct 2 ms 4552 KB Output is correct
10 Correct 2 ms 4436 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 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 4436 KB Output is correct
6 Correct 2 ms 4448 KB Output is correct
7 Correct 2 ms 4436 KB Output is correct
8 Correct 3 ms 4436 KB Output is correct
9 Correct 2 ms 4552 KB Output is correct
10 Correct 2 ms 4436 KB Output is correct
11 Correct 3 ms 4564 KB Output is correct
12 Correct 4 ms 4564 KB Output is correct
13 Correct 2 ms 4436 KB Output is correct
14 Correct 6 ms 4564 KB Output is correct
15 Correct 7 ms 4564 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 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 4436 KB Output is correct
6 Correct 2 ms 4448 KB Output is correct
7 Correct 2 ms 4436 KB Output is correct
8 Correct 3 ms 4436 KB Output is correct
9 Correct 2 ms 4552 KB Output is correct
10 Correct 2 ms 4436 KB Output is correct
11 Correct 3 ms 4564 KB Output is correct
12 Correct 4 ms 4564 KB Output is correct
13 Correct 2 ms 4436 KB Output is correct
14 Correct 6 ms 4564 KB Output is correct
15 Correct 7 ms 4564 KB Output is correct
16 Correct 65 ms 7288 KB Output is correct
17 Correct 46 ms 7196 KB Output is correct
18 Correct 66 ms 7200 KB Output is correct
19 Execution timed out 1088 ms 6492 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #5
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 3 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 4436 KB Output is correct
6 Correct 2 ms 4448 KB Output is correct
7 Correct 2 ms 4436 KB Output is correct
8 Correct 3 ms 4436 KB Output is correct
9 Correct 2 ms 4552 KB Output is correct
10 Correct 2 ms 4436 KB Output is correct
11 Correct 3 ms 4564 KB Output is correct
12 Correct 4 ms 4564 KB Output is correct
13 Correct 2 ms 4436 KB Output is correct
14 Correct 6 ms 4564 KB Output is correct
15 Correct 7 ms 4564 KB Output is correct
16 Correct 65 ms 7288 KB Output is correct
17 Correct 46 ms 7196 KB Output is correct
18 Correct 66 ms 7200 KB Output is correct
19 Execution timed out 1088 ms 6492 KB Time limit exceeded
20 Halted 0 ms 0 KB -