Submission #221202

#	Time	Username	Problem	Language	Result	Execution time	Memory
221202		Gareth618	Zalmoxis (BOI18_zalmoxis)	C++14	0 / 100	315 ms	9024 KiB

zalmoxis

#include <fstream>
#define NMAX 1000010
 
std::ifstream fin("zalmoxis.in");
std::ofstream fout("zalmoxis.out");
 
int len;
int v[NMAX];
bool spc[NMAX];
 
int top;
int st[NMAX];
 
inline int min(int x, int y) {
    return x < y ? x : y;
}
 
void print(int val, int cnt) {
    if (cnt == 1) {
        fout << val << ' ';
        return;
    }
    if (cnt == 2) {
        fout << val - 1 << ' ' << val - 1 << ' ';
        return;
    }
 
    int nr = (1 << (val - 1));
    if (cnt <= nr + 1) {
        fout << val - 1 << ' ';
        print(val - 1, cnt - 1);
    }
    else {
        print(val - 1, nr);
        print(val - 1, cnt - nr);
    }
}
 
int main() {
    int n, k; fin >> n >> k;
    for (int i = 0; i < n; i++) {
        int x; fin >> 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])
            fout << v[i] << ' ';
        else {
            print(v[i], min(++k, (1 << v[i])));
            if (k >= (1 << v[i]))
                k -= (1 << v[i]);
            else
                k = 0;
        }
 
    fout << '\n';
    fout.close();
    return 0;
}

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