oj.uz

Submission #375941

# Submission time Handle Problem Language Result Execution time Memory
375941 2021-03-10T09:50:04 Z EndRay Zalmoxis (BOI18_zalmoxis) C++17
100 / 100
 187 ms 39664 KB 
#include<bits/stdc++.h>
#define x first
#define y second

using namespace std;

int n, k;
vector<pair<int, int>> ans;
vector<int> s;

void push(int x){
    if(s.empty())
        s.push_back(x);
    else if(s.back() == x){
        s.pop_back();
        push(x+1);
    }
    else s.push_back(x);
}

void combine(){
    ans.emplace_back(s.back(), 1);
    --k;
    push(s.back());
}

void try_push(int x){
    while(!s.empty() && s.back() < x)
        combine();
    ans.emplace_back(x, 0);
    push(x);
}

void print(pair<int, int> p){
    if(!p.y || !k || p.x == 1){
        cout << p.x << " ";
        return;
    }
    --k;
    print({p.x-1, 1});
    print({p.x-1, 1});
}

int main(){
    ios_base::sync_with_stdio(false);
    cout.tie(0);
    cin.tie(0);
    cin >> n >> k;
    for(int i = 0; i < n; ++i){
        int x;
        cin >> x;
        try_push(x);
    }
    while(s.back() < 30)
        combine();
    for(auto el : ans)
        print(el);
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 187 ms 12496 KB Output is correct
2 Correct 180 ms 12520 KB Output is correct
3 Correct 184 ms 12496 KB Output is correct
4 Correct 186 ms 12628 KB Output is correct
5 Correct 181 ms 12624 KB Output is correct
6 Correct 180 ms 12496 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 180 ms 12448 KB Output is correct
2 Correct 186 ms 12624 KB Output is correct
3 Correct 182 ms 12496 KB Output is correct
4 Correct 180 ms 12496 KB Output is correct
5 Correct 181 ms 12548 KB Output is correct
6 Correct 180 ms 12496 KB Output is correct
7 Correct 184 ms 12720 KB Output is correct
8 Correct 183 ms 12624 KB Output is correct
9 Correct 166 ms 11640 KB Output is correct
10 Correct 140 ms 24924 KB Output is correct
11 Correct 147 ms 9696 KB Output is correct
12 Correct 128 ms 39532 KB Output is correct
13 Correct 129 ms 39664 KB Output is correct
14 Correct 96 ms 2412 KB Output is correct