oj.uz

Submission #381027

# Submission time Handle Problem Language Result Execution time Memory
381027 2021-03-24T09:03:46 Z VodkaInTheJar Zalmoxis (BOI18_zalmoxis) C++14
35 / 100
 808 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]);
}

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.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 781 ms 92620 KB Output is correct
2 Correct 800 ms 92524 KB Output is correct
3 Correct 795 ms 92568 KB Output is correct
4 Correct 793 ms 92520 KB Output is correct
5 Correct 795 ms 92524 KB Output is correct
6 Correct 784 ms 92524 KB Output is correct

Subtask #2
5.0 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 796 ms 92652 KB Unexpected end of file - int32 expected
2 Correct 789 ms 92652 KB Output is correct
3 Incorrect 806 ms 92524 KB Unexpected end of file - int32 expected
4 Incorrect 800 ms 92608 KB Unexpected end of file - int32 expected
5 Incorrect 792 ms 92468 KB Unexpected end of file - int32 expected
6 Incorrect 808 ms 92524 KB Unexpected end of file - int32 expected
7 Incorrect 795 ms 92524 KB Unexpected end of file - int32 expected
8 Incorrect 805 ms 92524 KB Unexpected end of file - int32 expected
9 Incorrect 749 ms 82900 KB Unexpected end of file - int32 expected
10 Incorrect 323 ms 46556 KB Unexpected end of file - int32 expected
11 Incorrect 514 ms 61404 KB Unexpected end of file - int32 expected
12 Incorrect 15 ms 23788 KB Unexpected end of file - int32 expected
13 Incorrect 15 ms 23788 KB Unexpected end of file - int32 expected
14 Incorrect 15 ms 23788 KB Unexpected end of file - int32 expected