Submission #865641

#	Time	Username	Problem	Language	Result	Execution time	Memory
865641		Blagoj	Zalmoxis (BOI18_zalmoxis)	C++17	100 / 100	116 ms	59584 KiB

zalmoxis

#include <bits/stdc++.h>

using namespace std;

#define endl '\n'
#define ll long long
#define all(x) x.begin(), x.end()

void CPS(vector<int> &v) {
    while (v.size() > 1) {
        int sz = v.size();
        if (v[sz - 1] == v[sz - 2]) {
            v.pop_back();
            v[sz - 2]++;
        }
        else break;
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n, k;
    cin >> n >> k;
    vector<int> v(n);
    for (int i = 0; i < n; i++) cin >> v[i];
    v.push_back(30);
    n++;
    vector<int> stk;
    vector<pair<int, int>> ans;
    for (int i = 0; i < n; i++) {
        while (stk.size() && stk.back() < v[i]) {
            int val = stk.back();
            ans.push_back({val, 1});
            stk.push_back(val);
            CPS(stk);
        }
        stk.push_back(v[i]);
        ans.push_back({v[i], 0});
        CPS(stk);
    }
    ans.pop_back();
    for (auto x : ans) k -= x.second;
    vector<int> res;
    function<void(int)> Add = [&] (int x) {
        if (k == 0 || x == 1) res.push_back(x);
        else {
            k--;
            Add(x - 1);
            Add(x - 1);
        }
    };
    for (auto x : ans) {
        if (x.second == 1) {
            Add(x.first);
        }
        else res.push_back(x.first);
    }
    for (auto x : res) cout << x << " ";
}

• Subtask 1: 30 / 30
• Subtask 2: 70 / 70