oj.uz

Submission #139113

# Submission time Handle Problem Language Result Execution time Memory
139113 2019-07-31T09:35:09 Z mlyean00 Zalmoxis (BOI18_zalmoxis) C++14
100 / 100
 236 ms 35392 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<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.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 224 ms 34220 KB Output is correct
2 Correct 223 ms 34196 KB Output is correct
3 Correct 220 ms 34296 KB Output is correct
4 Correct 236 ms 34224 KB Output is correct
5 Correct 225 ms 34296 KB Output is correct
6 Correct 222 ms 34140 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 225 ms 34168 KB Output is correct
2 Correct 224 ms 34348 KB Output is correct
3 Correct 224 ms 34168 KB Output is correct
4 Correct 221 ms 34288 KB Output is correct
5 Correct 222 ms 34276 KB Output is correct
6 Correct 219 ms 34168 KB Output is correct
7 Correct 221 ms 34300 KB Output is correct
8 Correct 226 ms 34296 KB Output is correct
9 Correct 216 ms 35320 KB Output is correct
10 Correct 178 ms 35028 KB Output is correct
11 Correct 201 ms 35392 KB Output is correct
12 Correct 153 ms 33656 KB Output is correct
13 Correct 154 ms 33740 KB Output is correct
14 Correct 167 ms 33820 KB Output is correct