oj.uz

Submission #658033

# Submission time Handle Problem Language Result Execution time Memory
658033 2022-11-11T23:27:48 Z stevancv Zalmoxis (BOI18_zalmoxis) C++14
100 / 100
 148 ms 14320 KB 
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define sp ' '
#define en '\n'
#define smin(a, b) a = min(a, b)
#define smax(a, b) a = max(a, b)
using namespace std;
const int N = 3e3 + 2;
const int inf = 2e9;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, k;
    cin >> n >> k;
    vector<int> a(n + 1);
    a[n] = 30;
    stack<int> s;
    vector<pair<int, int>> ans;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    for (int i = 0; i <= n; i++) {
        if (i == 0) {
            ans.push_back({a[i], 0});
            s.push(a[i]);
            continue;
        }
        while (s.top() < a[i]) {
            int x = s.top();
            ans.push_back({x, 1});
            k--;
            s.push(x);
            while (s.size() > 1) {
                x = s.top(); s.pop();
                if (x == s.top()) s.top()++;
                else {s.push(x); break;}
            }
        }
        int x = a[i];
        ans.push_back({a[i], 0});
        s.push(a[i]);
        while (s.size() > 1) {
            x = s.top(); s.pop();
            if (x == s.top()) s.top()++;
            else {s.push(x); break;}
        }
    }
    function<void(int)> F = [&] (int x) {
        if (x == 0 || k == 0) {
            cout << x << sp;
            return;
        }
        k -= 1;
        F(x - 1); F(x - 1);
    };
    for (auto u : ans) {
        if (u.first == 30) break;
        if (u.second == 0) cout << u.first << sp;
        else F(u.first);
    }
    return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 14200 KB Output is correct
2 Correct 131 ms 14252 KB Output is correct
3 Correct 148 ms 14196 KB Output is correct
4 Correct 130 ms 14240 KB Output is correct
5 Correct 137 ms 14272 KB Output is correct
6 Correct 144 ms 14320 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 14232 KB Output is correct
2 Correct 144 ms 14188 KB Output is correct
3 Correct 132 ms 14276 KB Output is correct
4 Correct 136 ms 14256 KB Output is correct
5 Correct 131 ms 14272 KB Output is correct
6 Correct 129 ms 14216 KB Output is correct
7 Correct 134 ms 14256 KB Output is correct
8 Correct 132 ms 14312 KB Output is correct
9 Correct 131 ms 12888 KB Output is correct
10 Correct 91 ms 6964 KB Output is correct
11 Correct 129 ms 10596 KB Output is correct
12 Correct 69 ms 2208 KB Output is correct
13 Correct 77 ms 2264 KB Output is correct
14 Correct 75 ms 2232 KB Output is correct