oj.uz

Submission #139013

# Submission time Handle Problem Language Result Execution time Memory
139013 2019-07-31T07:43:30 Z mlyean00 Zalmoxis (BOI18_zalmoxis) C++17
30 / 100
 234 ms 64572 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();
        rem -= 1 << h;
        b.push_back(h);
        while (!st.empty() && st.top() == h) {
            st.pop();
            ++h;
        }
    }

    assert(rem == 0);

    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 227 ms 34296 KB Output is correct
2 Correct 234 ms 34272 KB Output is correct
3 Correct 232 ms 34296 KB Output is correct
4 Correct 234 ms 34296 KB Output is correct
5 Correct 227 ms 34264 KB Output is correct
6 Correct 229 ms 34312 KB Output is correct

Subtask #2
0 / 70.0

# Verdict Execution time Memory Grader output
1 Runtime error 187 ms 64564 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 186 ms 64572 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 202 ms 64280 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 186 ms 64348 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 185 ms 64436 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 186 ms 64496 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 184 ms 64376 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 202 ms 64572 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 164 ms 60152 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 74 ms 28172 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Runtime error 114 ms 42844 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Runtime error 3 ms 508 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Runtime error 3 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Runtime error 2 ms 632 KB Execution killed with signal 11 (could be triggered by violating memory limits)