oj.uz

Submission #139105

# Submission time Handle Problem Language Result Execution time Memory
139105 2019-07-31T09:30:30 Z mlyean00 Zalmoxis (BOI18_zalmoxis) C++14
95 / 100
 1000 ms 35204 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);
        if (left == 0) break;
    }

    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 237 ms 33832 KB Output is correct
2 Correct 227 ms 33784 KB Output is correct
3 Correct 221 ms 33784 KB Output is correct
4 Correct 217 ms 33784 KB Output is correct
5 Correct 219 ms 33952 KB Output is correct
6 Correct 219 ms 33776 KB Output is correct

Subtask #2
65.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 229 ms 33920 KB Output is correct
2 Correct 223 ms 34036 KB Output is correct
3 Correct 232 ms 34000 KB Output is correct
4 Correct 226 ms 33852 KB Output is correct
5 Correct 226 ms 33784 KB Output is correct
6 Correct 225 ms 33784 KB Output is correct
7 Correct 235 ms 33844 KB Output is correct
8 Correct 225 ms 33824 KB Output is correct
9 Correct 263 ms 34944 KB Output is correct
10 Execution timed out 1014 ms 34904 KB Time limit exceeded
11 Correct 325 ms 35204 KB Output is correct
12 Correct 161 ms 33804 KB Output is correct
13 Correct 155 ms 33700 KB Output is correct
14 Correct 170 ms 33700 KB Output is correct