oj.uz

Submission #139044

# Submission time Handle Problem Language Result Execution time Memory
139044 2019-07-31T08:32:05 Z mlyean00 Zalmoxis (BOI18_zalmoxis) C++14
95 / 100
 1000 ms 34508 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.empty()) {
        int h = st.top();
        if (h == 30) break;
        rem -= 1 << h;
        b.push_back(h);
        while (h == st.top()) {
            st.pop();
            if (h == 30) break;
            ++h;
        }
        st.push(h);
    }

    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 247 ms 34296 KB Output is correct
2 Correct 233 ms 34324 KB Output is correct
3 Correct 237 ms 34508 KB Output is correct
4 Correct 232 ms 34436 KB Output is correct
5 Correct 230 ms 34388 KB Output is correct
6 Correct 229 ms 34360 KB Output is correct

Subtask #2
65.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 232 ms 34180 KB Output is correct
2 Correct 243 ms 34424 KB Output is correct
3 Execution timed out 1056 ms 32376 KB Time limit exceeded
4 Correct 233 ms 34372 KB Output is correct
5 Correct 241 ms 34300 KB Output is correct
6 Correct 250 ms 34296 KB Output is correct
7 Correct 233 ms 34312 KB Output is correct
8 Correct 232 ms 34372 KB Output is correct
9 Correct 220 ms 34296 KB Output is correct
10 Correct 179 ms 33968 KB Output is correct
11 Correct 207 ms 34040 KB Output is correct
12 Correct 152 ms 33712 KB Output is correct
13 Correct 155 ms 33700 KB Output is correct
14 Correct 171 ms 33740 KB Output is correct