oj.uz

Submission #139039

# Submission time Handle Problem Language Result Execution time Memory
139039 2019-07-31T08:26:08 Z mlyean00 Zalmoxis (BOI18_zalmoxis) C++14
95 / 100
 1000 ms 34680 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 (!st.empty() && h == st.top()) {
                ++h;
                st.pop();
            }
            st.push(h);
        }
    }

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

    vector<int> v;
    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 232 ms 34656 KB Output is correct
2 Correct 232 ms 34556 KB Output is correct
3 Correct 237 ms 34620 KB Output is correct
4 Correct 230 ms 34552 KB Output is correct
5 Correct 232 ms 34672 KB Output is correct
6 Correct 229 ms 34412 KB Output is correct

Subtask #2
65.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 233 ms 34488 KB Output is correct
2 Correct 231 ms 34556 KB Output is correct
3 Execution timed out 1075 ms 32348 KB Time limit exceeded
4 Correct 234 ms 34552 KB Output is correct
5 Correct 231 ms 34680 KB Output is correct
6 Correct 231 ms 34564 KB Output is correct
7 Correct 229 ms 34552 KB Output is correct
8 Correct 239 ms 34520 KB Output is correct
9 Correct 220 ms 34568 KB Output is correct
10 Correct 178 ms 34296 KB Output is correct
11 Correct 196 ms 34296 KB Output is correct
12 Correct 152 ms 33784 KB Output is correct
13 Correct 152 ms 33656 KB Output is correct
14 Correct 169 ms 33704 KB Output is correct