oj.uz

Submission #108105

# Submission time Handle Problem Language Result Execution time Memory
108105 2019-04-27T10:39:15 Z brcode Zalmoxis (BOI18_zalmoxis) C++14
100 / 100
 985 ms 54564 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;
vector<int> v1;
vector<int> ans;
set<int> s1;
int idx;
void solve(int curr,int level){
    if(v1[idx] == level){
        ans.push_back(curr);
        idx++;
        return;
    }
    solve(2*curr,level-1);
    if(idx == v1.size()||level<=v1[idx]){
        s1.insert(2*curr+1);
        return;
    }
    solve(2*curr+1,level-1);
}
void getans(int curr,int level){
    if(binary_search(ans.begin(),ans.end(),curr)){
        cout<<level<<" ";
        return;
    }
    getans(2*curr,level-1);
    getans(2*curr+1,level-1);
}
int main(){
    int n,k;
    cin>>n>>k;
    for(int i=0;i<n;i++){
        int x;
        cin>>x;
        v1.push_back(x);
    }
    solve(1,30);
    while(s1.size()<k){
        auto hold = *s1.begin();
        s1.erase(hold);
        s1.insert((hold)*2);
        s1.insert((hold)*2 +1);
    }
    for(auto i:s1){
        ans.push_back(i);
    }
    sort(ans.begin(),ans.end());
    getans(1,30);
}

Compilation message

zalmoxis.cpp: In function 'void solve(int, int)':
zalmoxis.cpp:17:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(idx == v1.size()||level<=v1[idx]){
        ~~~~^~~~~~~~~~~~
zalmoxis.cpp: In function 'int main()':
zalmoxis.cpp:40:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(s1.size()<k){
           ~~~~~~~~~^~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 523 ms 12500 KB Output is correct
2 Correct 464 ms 12508 KB Output is correct
3 Correct 476 ms 12508 KB Output is correct
4 Correct 540 ms 12508 KB Output is correct
5 Correct 475 ms 12512 KB Output is correct
6 Correct 528 ms 12380 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 469 ms 12380 KB Output is correct
2 Correct 483 ms 12528 KB Output is correct
3 Correct 549 ms 12516 KB Output is correct
4 Correct 531 ms 12336 KB Output is correct
5 Correct 467 ms 12592 KB Output is correct
6 Correct 482 ms 12624 KB Output is correct
7 Correct 454 ms 12512 KB Output is correct
8 Correct 480 ms 12628 KB Output is correct
9 Correct 665 ms 20824 KB Output is correct
10 Correct 627 ms 41824 KB Output is correct
11 Correct 629 ms 33252 KB Output is correct
12 Correct 913 ms 54564 KB Output is correct
13 Correct 968 ms 54364 KB Output is correct
14 Correct 985 ms 54444 KB Output is correct