Submission #381027

#	Time	Username	Problem	Language	Result	Execution time	Memory
381027		VodkaInTheJar	Zalmoxis (BOI18_zalmoxis)	C++14	35 / 100	808 ms	92652 KiB

zalmoxis

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#define endl '\n'

using namespace std;

const int maxn = 1e6 + 3;

int n, k;
int a[maxn];

void read()
{
    cin >> n >> k;
    for (int i = 1; i <= n; i++)
    cin >> a[i];
}

int par[maxn], val[maxn], r[maxn], sz[maxn];
int find_root(int ver)
{
    if (ver == par[ver])
        return ver;

    return par[ver] = find_root(par[ver]);
}

vector <int> to_add[maxn];
void solve()
{
    for (int i = 1; i <= n; i++)
    {
        par[i] = i;
        val[i] = a[i];
        r[i] = i;
        sz[i] = 1;
    }

    set <pair <int, int> > s;
    for (int i = 1; i <= n; i++)
    s.insert({a[i], i});

    while ((int)s.size() > 1)
    {
        pair <int, int> curr = *s.begin();
        if (r[curr.second] == n || val[find_root(r[curr.second] + 1)] != curr.first)
        {
            to_add[r[curr.second]].push_back(curr.first);
            val[curr.second]++;
            s.erase(s.begin());
            s.insert({curr.first + 1, curr.second});
        }

        else
        {
            int root = find_root(r[curr.second] + 1);

            if (sz[root] < sz[curr.second])
            {
                par[root] = curr.second;
                r[curr.second] = r[root];
                val[curr.second]++;

                s.erase(s.begin());
                s.erase(s.find({curr.first, root}));
                s.insert({curr.first + 1, curr.second});
            }

            else
            {
                par[curr.second] = root;
                val[root]++;
                sz[root] += sz[curr.second];

                s.erase(s.begin());
                s.erase(s.find({curr.first, root}));
                s.insert({curr.first + 1, root});
            }
        }
    }

    vector <int> ans;
    for (int i = 1; i <= n; i++)
    {
        ans.push_back(a[i]);
        for (auto j: to_add[i])
            ans.push_back(j);
    }

    for (auto i: ans)
        cout << i << " ";
    cout << endl;
}

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

    read();
    solve();
}

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