Submission #607552

#	Time	Username	Problem	Language	Result	Execution time	Memory
607552		chonka	Zalmoxis (BOI18_zalmoxis)	C++98	100 / 100	156 ms	14296 KiB

zalmoxis

#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 (stderr)

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 / 30
• Subtask 2: 70 / 70