Lisäykset

#include <bits/stdc++.h>

using namespace std;

struct kohta_t {
    int lisäys;
    int määrä;
};

bool debug = 0;
void printtaa(const map<int, kohta_t>& data) {
    if (!debug) return;
    int luku = 0, määrä = 0;
    for (const auto& [_, kohta] : data) {
        luku += kohta.lisäys;
        for (int i = 0; i < kohta.määrä; ++i) {
            cout << luku << " ";
            määrä += 1;
        }
        cout << "| ";
    }
    cout << " (" << määrä << ")\n";
}

vector<int> brute_force(const map<int, int>& määrät, const vector<int>& muutokset) {
    multiset<int> luvut;
    for (const auto& [luku, määrä] : määrät) {
        for (int i = 0; i < määrä; ++i) {
            luvut.insert(luku);
        }
    }

    for (int muutettavia : muutokset) {
        vector<int> temp;
        for (int j = 0; j < muutettavia; ++j) {
            temp.push_back(*luvut.begin());
            luvut.erase(luvut.begin());
        }
        for (int x : temp) {
            luvut.insert(x + 1);
        }
    }

    return vector<int>(luvut.begin(), luvut.end());
}

vector<int> ratkaisu(const map<int, int>& määrät, const vector<int>& muutokset) {
    map<int, kohta_t> data;
    int kohta = 0, luku0 = 0;
    for (const auto& [luku, määrä] : määrät) {
        data[kohta] = {luku - luku0, määrä};
        kohta += määrä;
        luku0 = luku;
    }
    data[kohta] = {(int) muutokset.size() + 1, 0};

    for (int muutettavia : muutokset) {
        if (debug) cerr << muutettavia << "\n";
        printtaa(data);
        data.begin()->second.lisäys += 1;

        auto it = data.upper_bound(muutettavia);
        --it;
        it->second.lisäys -= 1;
        printtaa(data);

        muutettavia -= it->first;
        if (muutettavia > 0) {
            int ei_muutettavia = it->second.määrä - muutettavia;
            data.insert({it->first + ei_muutettavia, {1, muutettavia}});
            it->second.määrä = ei_muutettavia;

            auto it2 = next(next(it));
            if (it2 != data.end()) {
                it2->second.lisäys -= 1;
                printtaa(data);
                if (it2->second.lisäys == 0) {
                    prev(it2)->second.määrä += it2->second.määrä;
                    data.erase(it2);
                }
                printtaa(data);
            }
        }
        if (it != data.begin() && it->second.lisäys == 0) {
            prev(it)->second.määrä += it->second.määrä;
            data.erase(it);
            printtaa(data);
        }
    }

    vector<int> tulos;
    int luku = 0;
    for (const auto& [_, kohta] : data) {
        luku += kohta.lisäys;
        for (int i = 0; i < kohta.määrä; ++i) {
            tulos.push_back(luku);
        }
    }
    return tulos;
}

void kisa_main() {
    int n, m;
    cin >> n >> m;

    vector<int> luvut(n);
    for (int i = 0; i < n; ++i) {
        cin >> luvut[i];
    }

    vector<int> muutokset(m);
    for (int i = 0; i < m; ++i) {
        cin >> muutokset[i];
    }

    map<int, int> määrät;
    for (int i = 0; i < n; ++i) {
        määrät[luvut[i]]++;
    }

    vector<int> tulos = ratkaisu(määrät, muutokset);

    for (int luku : tulos) {
        cout << luku << " ";
    }
    cout << "\n";
}

void fuzz_main() {
    while (1) {
        int n = rand() % 20 + 1;
        int m = rand() % 20 + 1;
        multiset<int> luvut;
        for (int i = 0; i < n; ++i) {
            luvut.insert(rand() % 10);
        }
        vector<int> muutokset(m);
        for (int i = 0; i < m; ++i) {
            muutokset[i] = rand() % n + 1;
        }

        map<int, int> määrät;
        for (int i: luvut) {
            määrät[i]++;
        }

        cerr << n << " " << m << "\n";
        for (int i: luvut) {
            cerr << i << " ";
        }
        cerr << "\n";
        for (int i: muutokset) {
            cerr << i << " ";
        }
        cerr << "\n";
        vector<int> tulos = ratkaisu(määrät, muutokset);
        vector<int> tarkastus = brute_force(määrät, muutokset);

        if (tulos != tarkastus) {
            cerr << "VIRHE!\n";
            return;
        }
        cerr << "OK!\n";
    }
}

void test_main() {
    debug = 1;
    int n, m;
    cin >> n >> m;

    vector<int> luvut(n);
    for (int i = 0; i < n; ++i) {
        cin >> luvut[i];
    }

    vector<int> muutokset(m);
    for (int i = 0; i < m; ++i) {
        cin >> muutokset[i];
    }

    map<int, int> määrät;
    for (int i = 0; i < n; ++i) {
        määrät[luvut[i]]++;
    }

    vector<int> tulos = ratkaisu(määrät, muutokset);
    vector<int> tarkastus = brute_force(määrät, muutokset);

    for (int luku : tulos) {
        cout << luku << " ";
    }
    cout << "\n";
    for (int luku : tarkastus) {
        cout << luku << " ";
    }
    cout << "\n";
}

int main() {
    kisa_main();
}

Test 1

Group: 1, 2, 3

Verdict: ACCEPTED

Test 2

Group: 1, 2, 3

Verdict: ACCEPTED

Test 3

Group: 1, 3

Verdict: ACCEPTED

Test 4

Group: 1, 3

Verdict: ACCEPTED

Test 5

Group: 1, 3

Verdict: ACCEPTED

Test 6

Group: 2, 3

Verdict: ACCEPTED

Test 7

Group: 3

Verdict: ACCEPTED

Test 8

Group: 3

Verdict: ACCEPTED

Test 9

Group: 3

Verdict: ACCEPTED

Test 10

Group: 3

Verdict: ACCEPTED

Test 11

Group: 3

Verdict: ACCEPTED