Submission #221204

#	Time	Username	Problem	Language	Result	Execution time	Memory
221204		Gareth618	Zalmoxis (BOI18_zalmoxis)	C++14	100 / 100	334 ms	7288 KiB

zalmoxis

#include <bits/stdc++.h>
using namespace std;

const int NMAX = 1e6 + 1;

int len;
int v[NMAX];
bool spc[NMAX];

int top;
int st[NMAX];

void print(int val, int cnt) {
    if (cnt == 1) {
        cout << val << ' ';
        return;
    }
    if (cnt == 2) {
        cout << val - 1 << ' ' << val - 1 << ' ';
        return;
    }

    int nr = (1 << (val - 1));
    if (cnt <= nr + 1) {
        cout << val - 1 << ' ';
        print(val - 1, cnt - 1);
    }
    else {
        print(val - 1, nr);
        print(val - 1, cnt - nr);
    }
}

int main() {
    int n, k; cin >> n >> k;
    for (int i = 0; i < n; i++) {
        int x; cin >> x;
        if (!top || st[top] >= x) {
            v[++len] = st[++top] = x;
            while (top >= 2 && st[top - 1] == st[top])
                st[--top]++;
        }
        else {
            while (st[top] < x) {
                v[++len] = st[top + 1] = st[top]; top++; spc[len] = true;
                while (top >= 2 && st[top - 1] == st[top])
                    st[--top]++;
            }
            v[++len] = st[++top] = x;
            while (top >= 2 && st[top - 1] == st[top])
                st[--top]++;
        }
    }

    while (top >= 2 && st[top - 1] == st[top])
        st[--top]++;
    while (st[top] < 30) {
        v[++len] = st[top + 1] = st[top]; top++; spc[len] = true;
        while (top >= 2 && st[top - 1] == st[top])
            st[--top]++;
    }

    k -= len - n;
    for (int i = 1; i <= len; i++)
        if (!spc[i])
            cout << v[i] << ' ';
        else {
            print(v[i], min(++k, (1 << v[i])));
            if (k >= (1 << v[i]))
                k -= (1 << v[i]);
            else
                k = 0;
        } 
    cout << '\n';
    return 0;
}

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