oj.uz

Submission #69968

# Submission time Handle Problem Language Result Execution time Memory
69968 2018-08-22T07:13:17 Z vanogam Zalmoxis (BOI18_zalmoxis) C++14
100 / 100
 727 ms 99548 KB 
#include<bits/stdc++.h>
using namespace std;
int a,s,d[1000002],f,g,h,j,k,l,i,n,m;
struct tre{
    int val;
    tre *L;
    tre *R;
    tre(){
        L=NULL;
        R=NULL;
        val=0;
    }
};
tre *root;
void bld(tre *&it,int lv){
    it=new tre();
    if(!it->L && !it->R && lv==d[a]) {it->val=1;a++;return;}
    if(lv>d[a]) bld(it->L,lv-1);
    if(a==n) {if(!it->R) h++;return;}
    if(it->L && lv>d[a]) return bld(it->R,lv-1);
    if(!it->R) h++;
}

void fnd(tre *&it,int lv){
    if(it->val) {cout<<lv<<" ";return;}
    if(!it->L) {
        if(h==k || lv==0) {cout<<lv<<" ";return;}
        h++;
        it->L=new tre();
        it->R=new tre();
    }
    fnd(it->L,lv-1);
    if(!it->R) it->R=new tre();
    fnd(it->R,lv-1);
}
main(){
    ios::sync_with_stdio(0);
    cin>>n>>k;
    for(i=0;i<n;i++){
        cin>>d[i];
    }

    bld(root,30);
    //cout<<h<<"*";
    fnd(root,30);
}

Compilation message

zalmoxis.cpp:36:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(){
      ^

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 363 ms 71040 KB Output is correct
2 Correct 372 ms 73204 KB Output is correct
3 Correct 360 ms 75348 KB Output is correct
4 Correct 727 ms 77436 KB Output is correct
5 Correct 359 ms 79456 KB Output is correct
6 Correct 354 ms 81396 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 404 ms 83508 KB Output is correct
2 Correct 384 ms 85600 KB Output is correct
3 Correct 421 ms 87640 KB Output is correct
4 Correct 390 ms 89924 KB Output is correct
5 Correct 403 ms 91996 KB Output is correct
6 Correct 365 ms 94108 KB Output is correct
7 Correct 399 ms 96168 KB Output is correct
8 Correct 394 ms 98260 KB Output is correct
9 Correct 352 ms 98964 KB Output is correct
10 Correct 295 ms 98964 KB Output is correct
11 Correct 354 ms 99548 KB Output is correct
12 Correct 235 ms 99548 KB Output is correct
13 Correct 242 ms 99548 KB Output is correct
14 Correct 242 ms 99548 KB Output is correct