Submission #138986

#	Time	Username	Problem	Language	Result	Execution time	Memory
138986		mlyean00	Zalmoxis (BOI18_zalmoxis)	C++17	30 / 100	171 ms	10616 KiB

zalmoxis

#ifdef DEBUG
#include "debug.hpp"
#else
#pragma GCC optimize("Ofast")
#define trace(...)
#include <bits/stdc++.h>
#define endl '\n'
#endif

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }

    if (k == 1) {
        int rem = 1 << 30;
        for (int i = 0; i < n; ++i) {
            rem -= 1 << a[i];
        }
        int lost = __builtin_ctz(rem);

        stack<int> st;
        int i;
        for (i = 0; i < n; ++i) {
            if (st.empty()) {
                st.push(a[i]);
            } else {
                if (a[i] == st.top()) {
                    int k = a[i];
                    while (!st.empty() && k == st.top()) {
                        k = st.top() + 1;
                        st.pop();
                    }
                    st.push(k);
                } else if (a[i] < st.top()) {
                    st.push(a[i]);
                } else {
                    break;
                }
            }
        }
        a.insert(a.begin() + i, lost);
        for (int j = 0; j < n + k; ++j) {
            cout << a[j] << ' ';
        }
    } else {
        assert(false);
    }

    return 0;
}

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