oj.uz

Submission #97262

# Submission time Handle Problem Language Result Execution time Memory
97262 2019-02-14T16:47:31 Z MohamedAhmed0 Zalmoxis (BOI18_zalmoxis) C++14
100 / 100
 961 ms 54464 KB 
#include <bits/stdc++.h>

using namespace std ;

const int MAX = 2e6 + 10 ;
int idx ;
vector<int>v ;
int n , k ;
vector<int>ans ;
set<int>s ;


void solve(int node , int level)
{
    if(level == v[idx])
    {
        idx++;
        ans.push_back(node) ;
        return ;
    }
    solve(node * 2 , level - 1) ;
    if(idx == v.size() || level <= v[idx])
    {
        s.insert(node * 2 + 1) ;
        return ;
    }
    solve(node * 2 + 1 , level - 1) ;
}

void print_solution(int node , int level)
{
    if(binary_search(ans.begin() , ans.end() , node))
    {
        cout<<level<<" ";
        return ;
    }
    print_solution(node * 2 , level - 1) ;
    print_solution(node * 2 + 1 , level - 1) ;
}

int main()
{
    scanf("%d %d" , &n , &k) ;
    for(int i = 0 ; i < n ; ++i)
    {
        int x ;
        scanf("%d" , &x) ;
        v.push_back(x) ;
    }
    solve(1 , 30) ;
    while(s.size() < k)
    {
        int now = *s.begin() ;
        s.erase(now) ;
        s.insert(now * 2) ;
        s.insert(now * 2 + 1) ;
    }
    for(auto &i : s)
        ans.push_back(i) ;
    sort(ans.begin() , ans.end()) ;
    return print_solution(1 , 30) , 0;
}

Compilation message

zalmoxis.cpp: In function 'void solve(int, int)':
zalmoxis.cpp:22:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(idx == v.size() || level <= v[idx])
        ~~~~^~~~~~~~~~~
zalmoxis.cpp: In function 'int main()':
zalmoxis.cpp:51:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(s.size() < k)
           ~~~~~~~~~^~~
zalmoxis.cpp:43:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d" , &n , &k) ;
     ~~~~~^~~~~~~~~~~~~~~~~~~
zalmoxis.cpp:47:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d" , &x) ;
         ~~~~~^~~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 417 ms 10460 KB Output is correct
2 Correct 423 ms 10592 KB Output is correct
3 Correct 438 ms 10384 KB Output is correct
4 Correct 434 ms 10456 KB Output is correct
5 Correct 436 ms 10588 KB Output is correct
6 Correct 478 ms 10588 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 416 ms 10332 KB Output is correct
2 Correct 519 ms 10508 KB Output is correct
3 Correct 448 ms 10460 KB Output is correct
4 Correct 448 ms 10376 KB Output is correct
5 Correct 458 ms 10460 KB Output is correct
6 Correct 438 ms 10484 KB Output is correct
7 Correct 524 ms 10576 KB Output is correct
8 Correct 475 ms 10552 KB Output is correct
9 Correct 473 ms 19000 KB Output is correct
10 Correct 744 ms 41048 KB Output is correct
11 Correct 570 ms 32068 KB Output is correct
12 Correct 957 ms 54388 KB Output is correct
13 Correct 953 ms 54448 KB Output is correct
14 Correct 961 ms 54464 KB Output is correct