oj.uz

Submission #228047

# Submission time Handle Problem Language Result Execution time Memory
228047 2020-04-29T17:28:07 Z mohamedsobhi777 Zalmoxis (BOI18_zalmoxis) C++14
35 / 100
 322 ms 6628 KB 
#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 = 100 , 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.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 274 ms 6472 KB Output is correct
2 Correct 255 ms 6392 KB Output is correct
3 Correct 247 ms 6520 KB Output is correct
4 Correct 264 ms 6520 KB Output is correct
5 Correct 281 ms 6628 KB Output is correct
6 Correct 308 ms 6520 KB Output is correct

Subtask #2
5.0 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 206 ms 4344 KB Unexpected end of file - int32 expected
2 Correct 281 ms 6444 KB Output is correct
3 Incorrect 292 ms 6520 KB not a zalsequence
4 Incorrect 219 ms 4216 KB Unexpected end of file - int32 expected
5 Incorrect 322 ms 6520 KB not a zalsequence
6 Incorrect 299 ms 6480 KB not a zalsequence
7 Incorrect 231 ms 4344 KB Unexpected end of file - int32 expected
8 Incorrect 212 ms 4344 KB Unexpected end of file - int32 expected
9 Incorrect 196 ms 3576 KB Unexpected end of file - int32 expected
10 Incorrect 92 ms 1664 KB Unexpected end of file - int32 expected
11 Incorrect 131 ms 2424 KB Unexpected end of file - int32 expected
12 Incorrect 5 ms 384 KB Unexpected end of file - int32 expected
13 Incorrect 5 ms 384 KB Unexpected end of file - int32 expected
14 Incorrect 5 ms 384 KB Unexpected end of file - int32 expected