Submission #1144477

#	Time	Username	Problem	Language	Result	Execution time	Memory
1144477		crafticat	Zalmoxis (BOI18_zalmoxis)	C++20	15 / 100	420 ms	66120 KiB

zalmoxis

#include <bits/stdc++.h>
using namespace std;

#define F0R(i,n) for(int i=0;i<n;i++)
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define ROF(i,a,b) for(int i=b - 1;i>=a;i--)

template<typename T>
using V = vector<T>;
using vi = V<int>;
using pi = pair<int,int>;
const int INF=1e9+7;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr);

    int n, k; cin >> n >> k;
    vi arr(n);
    F0R(i, n)
        cin >> arr[i];

    V<V<pi>> sets(31);

    F0R(i, n) {
        sets[arr[i]].emplace_back(i, i + 1);
    }

    V<pi> newArr;
    multiset<pi, greater<>> fakes;
    F0R(i, n) {
        newArr.emplace_back(i, arr[i]);
    }

    F0R(s, 30) {
        sort(sets[s].begin(), sets[s].end());
        V<bool> vis(sets.size(), false);

        F0R(i, sets[s].size()) {
            if (vis[i]) continue;
            if (i + 1 < sets[s].size() and sets[s][i].second == sets[s][i + 1].first) {
                vis[i + 1] = 1;
                sets[s + 1].emplace_back(sets[s][i].first, sets[s][i + 1].second);
            } else {
                fakes.insert({s, sets[s][i].second});
                sets[s + 1].emplace_back(sets[s][i].first, sets[s][i].second);
            }
        }
    }
    if (fakes.empty()) exit(5);

    while (fakes.size() < k) {
        auto it = fakes.begin();
        auto [x, i] = *it;
        fakes.erase(it);
        fakes.insert({x - 1, i});
        fakes.insert({x - 1, i});
    }
    for (auto [a,b] : fakes) {
        newArr.emplace_back(b,a);
    }

    sort(newArr.begin(), newArr.end());
    vi ans;
    for (auto [i,x] : newArr) {
        ans.push_back(x);
    }

    F0R(i, n + k) cout << ans[i] << " ";

    return 0;
}

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