oj.uz

답안 #139030

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
139030 2019-07-31T08:03:44 Z mlyean00 Zalmoxis (BOI18_zalmoxis) C++14
90 / 100
 234 ms 63864 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;
        }
        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

# 결과 실행 시간 메모리 Grader output
1 Correct 231 ms 33784 KB Output is correct
2 Correct 231 ms 33956 KB Output is correct
3 Correct 228 ms 33784 KB Output is correct
4 Correct 229 ms 33788 KB Output is correct
5 Correct 230 ms 33848 KB Output is correct
6 Correct 226 ms 33784 KB Output is correct

Subtask #2
60.0 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Correct 227 ms 33784 KB Output is correct
2 Runtime error 185 ms 63864 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 187 ms 63796 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Correct 228 ms 33904 KB Output is correct
5 Correct 228 ms 33784 KB Output is correct
6 Correct 234 ms 33784 KB Output is correct
7 Correct 233 ms 33912 KB Output is correct
8 Correct 233 ms 33804 KB Output is correct
9 Correct 216 ms 33832 KB Output is correct
10 Correct 178 ms 33656 KB Output is correct
11 Correct 199 ms 33656 KB Output is correct
12 Correct 151 ms 33684 KB Output is correct
13 Correct 151 ms 33784 KB Output is correct
14 Correct 156 ms 33656 KB Output is correct