oj.uz

Submission #221204

# Submission time Handle Problem Language Result Execution time Memory
221204 2020-04-09T16:53:24 Z Gareth618 Zalmoxis (BOI18_zalmoxis) C++14
100 / 100
 334 ms 7288 KB 
#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.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 315 ms 6392 KB Output is correct
2 Correct 311 ms 6340 KB Output is correct
3 Correct 326 ms 6496 KB Output is correct
4 Correct 315 ms 6392 KB Output is correct
5 Correct 308 ms 6392 KB Output is correct
6 Correct 309 ms 6392 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 314 ms 6392 KB Output is correct
2 Correct 316 ms 7288 KB Output is correct
3 Correct 334 ms 7288 KB Output is correct
4 Correct 328 ms 6392 KB Output is correct
5 Correct 308 ms 6392 KB Output is correct
6 Correct 304 ms 6392 KB Output is correct
7 Correct 310 ms 6392 KB Output is correct
8 Correct 314 ms 6392 KB Output is correct
9 Correct 270 ms 7032 KB Output is correct
10 Correct 162 ms 4592 KB Output is correct
11 Correct 208 ms 5624 KB Output is correct
12 Correct 91 ms 2296 KB Output is correct
13 Correct 87 ms 2296 KB Output is correct
14 Correct 88 ms 2296 KB Output is correct