oj.uz

Submission #228050

# Submission time Handle Problem Language Result Execution time Memory
228050 2020-04-29T17:49:26 Z mohamedsobhi777 Zalmoxis (BOI18_zalmoxis) C++14
35 / 100
 684 ms 11336 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 = 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.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 573 ms 8312 KB Output is correct
2 Correct 553 ms 8312 KB Output is correct
3 Correct 558 ms 8312 KB Output is correct
4 Correct 558 ms 8312 KB Output is correct
5 Correct 573 ms 8312 KB Output is correct
6 Correct 601 ms 8312 KB Output is correct

Subtask #2
5.0 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 684 ms 8480 KB not a zalsequence
2 Correct 551 ms 8312 KB Output is correct
3 Incorrect 656 ms 8312 KB not a zalsequence
4 Incorrect 658 ms 8316 KB not a zalsequence
5 Incorrect 656 ms 8312 KB not a zalsequence
6 Incorrect 650 ms 8312 KB not a zalsequence
7 Incorrect 649 ms 8312 KB not a zalsequence
8 Incorrect 652 ms 8312 KB not a zalsequence
9 Incorrect 629 ms 7544 KB not a zalsequence
10 Incorrect 478 ms 8532 KB not a zalsequence
11 Incorrect 547 ms 7152 KB not a zalsequence
12 Incorrect 350 ms 11212 KB not a zalsequence
13 Incorrect 361 ms 11336 KB not a zalsequence
14 Incorrect 384 ms 11336 KB not a zalsequence