oj.uz

Submission #139047

# Submission time Handle Problem Language Result Execution time Memory
139047 2019-07-31T08:37:00 Z mlyean00 Zalmoxis (BOI18_zalmoxis) C++17
95 / 100
 1000 ms 34484 KB 
#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;

    list<int> a;
    int rem = 1 << 30;
    for (int i = 0; i < n; ++i) {
        int tmp;
        cin >> tmp;
        a.push_back(tmp);
        rem -= 1 << tmp;
    }

    stack<int> st;
    st.push(30);
    for (auto it = a.begin(); it != a.end(); ++it) {
        if (*it < st.top()) {
            st.push(*it);
        } else if (*it == st.top()) {
            int h = st.top();
            while (h == st.top()) {
                st.pop();
                if (h == 30) break;
                ++h;
            }
            st.push(h);
        } else {
            int h = st.top();
            rem -= 1 << h;
            it = a.insert(it, h);
            while (h == st.top()) {
                st.pop();
                if (h == 30) break;
                ++h;
            }
            st.push(h);
        }
    }

    list<int> b;
    while (st.top() != 30) {
        int h = st.top();
        rem -= 1 << h;
        b.push_back(h);
        while (h == st.top()) {
            st.pop();
            if (h == 30) break;
            ++h;
        }
        st.push(h);
    }

    assert(rem >= 0);

    for (; rem; rem -= rem & -rem) {
        b.push_back(__builtin_ctz(rem));
    }

    int left = (n + k) - (a.size() + b.size());
    assert(left >= 0);

    auto it = b.begin();
    for (int i = 0; i < left; ++i) {
        while (*it == 0)
            ++it;
        --(*it);
        it = b.insert(it, *it);
    }

    a.splice(a.end(), b);

    copy(a.begin(), a.end(), ostream_iterator<int>(cout, " "));
    cout << endl;

    return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 228 ms 34424 KB Output is correct
2 Correct 234 ms 34440 KB Output is correct
3 Correct 226 ms 34424 KB Output is correct
4 Correct 228 ms 34484 KB Output is correct
5 Correct 231 ms 34424 KB Output is correct
6 Correct 226 ms 34344 KB Output is correct

Subtask #2
65.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 240 ms 34436 KB Output is correct
2 Correct 226 ms 34440 KB Output is correct
3 Execution timed out 1049 ms 32408 KB Time limit exceeded
4 Correct 226 ms 34440 KB Output is correct
5 Correct 240 ms 34332 KB Output is correct
6 Correct 226 ms 34348 KB Output is correct
7 Correct 226 ms 34336 KB Output is correct
8 Correct 228 ms 34388 KB Output is correct
9 Correct 220 ms 34428 KB Output is correct
10 Correct 190 ms 33988 KB Output is correct
11 Correct 194 ms 34340 KB Output is correct
12 Correct 151 ms 33660 KB Output is correct
13 Correct 149 ms 33712 KB Output is correct
14 Correct 151 ms 33588 KB Output is correct