Submission #228050

#	Time	Username	Problem	Language	Result	Execution time	Memory
228050		mohamedsobhi777	Zalmoxis (BOI18_zalmoxis)	C++14	35 / 100	684 ms	11336 KiB

zalmoxis

#include<bits/stdc++.h>

using namespace std ;

const int N = 1e6 + 7 ; 

int n , k ;
int a[N] ; 

int check(int x , bool build = 0 ){
    int j = 0 ; 
    stack<int> st ; 
    st.push(x) ; 
    int ret = 1 ; 
    while(j < n){
        if(st.size() == 0)return -1 ;
        int tp = st.top() ;st.pop() ; 
        if(tp < a[j]){
            if(build)cout<<tp <<" " ; 
            continue ; 
        }
        else if(tp == a[j]){
            if(build)cout<< tp <<" " ; 
            j++ ;
        }
        else{
            st.push(tp - 1) ; 
            st.push(tp -1) ; 
            ret++;
        }
    }
    
    if(build){
        while(st.size()){
            cout<<st.top()<<" " ; 
            st.pop() ; 
        }        
    }
    return ret - n ; 
}

int main(){
    ios_base::sync_with_stdio(0) ; 
    cin.tie(0) ; 
    //freopen("in.in" , "r" , stdin) ; 
    cin>>n>>k ; 
    for(int i = 0 ; i < n ; i++)
        cin>>a[i] ;
    int l = 1 , r = 2000000 , ans = 0 ; 
    while(l <=r ){
        int mid = (l + r) /2 ; 
        int chk = check(mid) ;
        if(chk < k){
            l = mid+1 ; 
        }else r = mid -1 , ans = mid; 
    }
    check(ans , 1 ) ; 
    return 0 ; 
} 

• Subtask 1: 30 / 30
• Subtask 2: 5 / 70