oj.uz

Submission #139103

# Submission time Handle Problem Language Result Execution time Memory
139103 2019-07-31T09:29:16 Z mlyean00 Zalmoxis (BOI18_zalmoxis) C++14
75 / 100
 1000 ms 35484 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;
    }

    vector<list<int>::iterator> expand;

    unsigned int st = 1 << 30;
    for (auto it = a.begin(); it != a.end(); ++it) {
        int h = __builtin_ctz(st);
        if (*it < h) {
            st |= 1 << *it;
        } else if (*it == h) {
            st += 1 << *it;
        } else {
            rem -= 1 << h;
            it = a.insert(it, h);
            expand.push_back(it);
            st += 1 << h;
        }
    }

    for (int h = __builtin_ctz(st); h < 30; h = __builtin_ctz(st)) {
        rem -= 1 << h;
        expand.push_back(a.insert(a.end(), h));
        st += 1 << h;
    }

    assert(rem >= 0);
    for (; rem; rem -= rem & -rem) {
        expand.push_back(a.insert(a.end(), __builtin_ctz(rem)));
    }

    int left = n + k - a.size();
    assert(left >= 0);

    for (auto it : expand) {
        list<int> b = {*it};
        auto it2 = b.begin();
        while (left > 0 && it2 != b.end()) {
            while (*it2 == 0 && it2 != b.end())
                ++it2;
            if (it2 == b.end()) break;

            --(*it2);
            it2 = b.insert(it2, *it2);
            --left;
        }
        b.splice(b.end(), a, next(it), a.end());
        a.pop_back();
        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 221 ms 35380 KB Output is correct
2 Correct 222 ms 35384 KB Output is correct
3 Correct 229 ms 35428 KB Output is correct
4 Correct 221 ms 35480 KB Output is correct
5 Correct 223 ms 35452 KB Output is correct
6 Correct 224 ms 35232 KB Output is correct

Subtask #2
45.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 239 ms 35244 KB Output is correct
2 Execution timed out 1075 ms 33144 KB Time limit exceeded
3 Execution timed out 1072 ms 33180 KB Time limit exceeded
4 Correct 257 ms 35324 KB Output is correct
5 Correct 243 ms 35448 KB Output is correct
6 Correct 230 ms 35484 KB Output is correct
7 Correct 241 ms 35384 KB Output is correct
8 Correct 239 ms 35256 KB Output is correct
9 Execution timed out 1064 ms 33984 KB Time limit exceeded
10 Execution timed out 1054 ms 33516 KB Time limit exceeded
11 Execution timed out 1065 ms 33892 KB Time limit exceeded
12 Correct 152 ms 33784 KB Output is correct
13 Correct 153 ms 33668 KB Output is correct
14 Correct 153 ms 33740 KB Output is correct