oj.uz

Submission #607552

# Submission time Handle Problem Language Result Execution time Memory
607552 2022-07-26T20:02:54 Z chonka Zalmoxis (BOI18_zalmoxis) C++
100 / 100
 156 ms 14296 KB 
#include<bits/stdc++.h>
using namespace std ;
typedef long long ll ;

const int MAXN = 1000007 ;

int n , k ;
int a[ MAXN ] ;

stack < int > s ;
vector < pair < int , int > > v ;

void solve ( ) {
    cin >> n >> k ;
    for ( int i = 1 ; i <= n ; ++ i ) {
        cin >> a[ i ] ;
    }
    int tp = 0 ; 
    for ( int i = 1 ; i <= n ; ++ i ) {
        int x = a[ i ] ;
        while ( s.empty ( ) == false && s.top ( ) < x ) {
            int y = s.top ( ) ;
            -- k ;
            v.push_back ( { y , 1 } ) ;
            while ( s.empty ( ) == false && s.top ( ) == y ) {
                s.pop ( ) ;
                ++ y ;
            }
            s.push ( y ) ;
        }
        v.push_back ( { x , 0 } ) ;
        while ( s.empty ( ) == false && s.top ( ) == x ) {
            ++ x ; s.pop ( ) ;
        }
        s.push ( x ) ;
    }
    while ( s.empty ( ) == false && s.top ( ) < 30 ) {
        int y = s.top ( ) ;
        -- k ;
        v.push_back ( { y , 1 } ) ;
        while ( s.empty ( ) == false && s.top ( ) == y ) {
            s.pop ( ) ;
            ++ y ;
        }
        s.push ( y ) ;
    }
    for ( auto [ x , type ] : v ) {
        if ( type == 0 ) { cout << x << " " ; }
        else {
            while ( s.empty ( ) == false ) { s.pop ( ) ; }
            s.push ( x ) ;
            while ( k > 0 && s.empty ( ) == false ) {
                int hh = s.top ( ) ; s.pop ( ) ;
                if ( hh == 0 ) { cout << "0 " ; }
                else {
                    -- k ;
                    s.push ( hh - 1 ) ; s.push ( hh - 1 ) ;
                }
            }
            while ( s.empty ( ) == false ) {
                cout << s.top ( ) << " " ;
                s.pop ( ) ;
            }
        }
    }
    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

zalmoxis.cpp: In function 'void solve()':
zalmoxis.cpp:47:16: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   47 |     for ( auto [ x , type ] : v ) {
      |                ^
zalmoxis.cpp:18:9: warning: unused variable 'tp' [-Wunused-variable]
   18 |     int tp = 0 ;
      |         ^~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 128 ms 14276 KB Output is correct
2 Correct 156 ms 14252 KB Output is correct
3 Correct 135 ms 14296 KB Output is correct
4 Correct 126 ms 14176 KB Output is correct
5 Correct 129 ms 14252 KB Output is correct
6 Correct 126 ms 14252 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 128 ms 14256 KB Output is correct
2 Correct 132 ms 14252 KB Output is correct
3 Correct 134 ms 14180 KB Output is correct
4 Correct 127 ms 14256 KB Output is correct
5 Correct 126 ms 14244 KB Output is correct
6 Correct 122 ms 14280 KB Output is correct
7 Correct 126 ms 14296 KB Output is correct
8 Correct 122 ms 14280 KB Output is correct
9 Correct 144 ms 12980 KB Output is correct
10 Correct 81 ms 6972 KB Output is correct
11 Correct 106 ms 10568 KB Output is correct
12 Correct 41 ms 2256 KB Output is correct
13 Correct 38 ms 2252 KB Output is correct
14 Correct 37 ms 2204 KB Output is correct