oj.uz

답안 #626889

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
626889 2022-08-11T23:23:03 Z chonka Swap (BOI16_swap) C++17
48 / 100
 1000 ms 7272 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 ] ;
        }
    }
}

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

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 ;
      |         ^~~

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 4436 KB Output is correct
2 Correct 2 ms 4436 KB Output is correct
3 Correct 3 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

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 4436 KB Output is correct
2 Correct 2 ms 4436 KB Output is correct
3 Correct 3 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 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 2 ms 4436 KB Output is correct

Subtask #3
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 4436 KB Output is correct
2 Correct 2 ms 4436 KB Output is correct
3 Correct 3 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 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 2 ms 4436 KB Output is correct
11 Correct 3 ms 4564 KB Output is correct
12 Correct 8 ms 4564 KB Output is correct
13 Correct 2 ms 4436 KB Output is correct
14 Correct 94 ms 4564 KB Output is correct
15 Correct 95 ms 4564 KB Output is correct

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 4436 KB Output is correct
2 Correct 2 ms 4436 KB Output is correct
3 Correct 3 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 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 2 ms 4436 KB Output is correct
11 Correct 3 ms 4564 KB Output is correct
12 Correct 8 ms 4564 KB Output is correct
13 Correct 2 ms 4436 KB Output is correct
14 Correct 94 ms 4564 KB Output is correct
15 Correct 95 ms 4564 KB Output is correct
16 Correct 769 ms 7272 KB Output is correct
17 Correct 539 ms 7248 KB Output is correct
18 Execution timed out 1031 ms 7256 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #5
0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 4436 KB Output is correct
2 Correct 2 ms 4436 KB Output is correct
3 Correct 3 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 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 2 ms 4436 KB Output is correct
11 Correct 3 ms 4564 KB Output is correct
12 Correct 8 ms 4564 KB Output is correct
13 Correct 2 ms 4436 KB Output is correct
14 Correct 94 ms 4564 KB Output is correct
15 Correct 95 ms 4564 KB Output is correct
16 Correct 769 ms 7272 KB Output is correct
17 Correct 539 ms 7248 KB Output is correct
18 Execution timed out 1031 ms 7256 KB Time limit exceeded
19 Halted 0 ms 0 KB -