Submission #139113

#	Time	Username	Problem	Language	Result	Execution time	Memory
139113		mlyean00	Zalmoxis (BOI18_zalmoxis)	C++14	100 / 100	236 ms	35392 KiB

zalmoxis

#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<vector<list<int>::iterator>> expand(31);

    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[h].push_back(it);
            st += 1 << h;
        }
    }

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

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

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

    for (int i = 30; i >= 0; --i) {
        for (auto it : expand[i]) {
            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;
        }
        if (left == 0) break;
    }

    copy(a.begin(), a.end(), ostream_iterator<int>(cout, " "));
    cout << endl;

    return 0;
}

• Subtask 1: 30 / 30
• Subtask 2: 70 / 70