Submission #138988

#	Time	Username	Problem	Language	Result	Execution time	Memory
138988		mlyean00	Zalmoxis (BOI18_zalmoxis)	C++14	30 / 100	169 ms	8568 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() || a[i] < st.top()) {
                st.push(a[i]);
            } else if (a[i] == st.top()) {
                int h = a[i];
                while (!st.empty() && h == st.top()) {
                    ++h;
                    st.pop();
                }
                st.push(h);
            } 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