oj.uz

Submission #139028

# Submission time Handle Problem Language Result Execution time Memory
139028 2019-07-31T07:55:09 Z mlyean00 Zalmoxis (BOI18_zalmoxis) C++17
45 / 100
 244 ms 63936 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()) {
                ++h;
                st.pop();
            }
            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;
        }
    }

    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 230 ms 33784 KB Output is correct
2 Correct 225 ms 33804 KB Output is correct
3 Correct 222 ms 33784 KB Output is correct
4 Correct 223 ms 33788 KB Output is correct
5 Correct 226 ms 33856 KB Output is correct
6 Correct 244 ms 33884 KB Output is correct

Subtask #2
15.0 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 239 ms 33788 KB not a zalsequence
2 Runtime error 184 ms 63936 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 183 ms 63864 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Incorrect 230 ms 33712 KB not a zalsequence
5 Incorrect 231 ms 33912 KB not a zalsequence
6 Incorrect 228 ms 33756 KB not a zalsequence
7 Incorrect 224 ms 33784 KB not a zalsequence
8 Incorrect 223 ms 33812 KB not a zalsequence
9 Incorrect 213 ms 33792 KB not a zalsequence
10 Incorrect 185 ms 33784 KB not a zalsequence
11 Incorrect 192 ms 33656 KB not a zalsequence
12 Correct 157 ms 33704 KB Output is correct
13 Correct 150 ms 33656 KB Output is correct
14 Correct 151 ms 33784 KB Output is correct