oj.uz

Submission #381028

# Submission time Handle Problem Language Result Execution time Memory
381028 2021-03-24T09:09:25 Z VodkaInTheJar Zalmoxis (BOI18_zalmoxis) C++14
100 / 100
 822 ms 92652 KB 
#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]);
}

int all;
vector <int> ans;
void dfs(int ver)
{
    if (ver == 0 || all == n + k)
    {
        ans.push_back(ver);
        return;
    }

    all++;
    dfs(ver-1);
    dfs(ver-1);
}

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 || s.begin()->first < 30)
    {
        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});
            }
        }
    }

    all = n;
    for (int i = 1; i <= n; i++)
    all += (int)to_add[i].size();

    for (int i = 1; i <= n; i++)
    {
        ans.push_back(a[i]);
        for (auto j: to_add[i])
            dfs(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.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 779 ms 92524 KB Output is correct
2 Correct 797 ms 92524 KB Output is correct
3 Correct 793 ms 92524 KB Output is correct
4 Correct 801 ms 92524 KB Output is correct
5 Correct 812 ms 92524 KB Output is correct
6 Correct 785 ms 92540 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 797 ms 92396 KB Output is correct
2 Correct 805 ms 92560 KB Output is correct
3 Correct 822 ms 92524 KB Output is correct
4 Correct 797 ms 92524 KB Output is correct
5 Correct 794 ms 92524 KB Output is correct
6 Correct 795 ms 92652 KB Output is correct
7 Correct 800 ms 92524 KB Output is correct
8 Correct 799 ms 92504 KB Output is correct
9 Correct 754 ms 83240 KB Output is correct
10 Correct 386 ms 49876 KB Output is correct
11 Correct 549 ms 63188 KB Output is correct
12 Correct 108 ms 30108 KB Output is correct
13 Correct 108 ms 29916 KB Output is correct
14 Correct 108 ms 30044 KB Output is correct