oj.uz

답안 #381026

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
381026 2021-03-24T09:00:37 Z VodkaInTheJar Zalmoxis (BOI18_zalmoxis) C++14
35 / 100
 837 ms 90736 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];
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;
    }

    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);
            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});
        }
    }

    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

# 결과 실행 시간 메모리 Grader output
1 Correct 793 ms 90732 KB Output is correct
2 Correct 819 ms 90584 KB Output is correct
3 Correct 777 ms 90604 KB Output is correct
4 Correct 778 ms 90616 KB Output is correct
5 Correct 763 ms 90732 KB Output is correct
6 Correct 788 ms 90604 KB Output is correct

Subtask #2
5.0 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 817 ms 90540 KB Unexpected end of file - int32 expected
2 Correct 773 ms 90644 KB Output is correct
3 Incorrect 812 ms 90604 KB Unexpected end of file - int32 expected
4 Incorrect 837 ms 90736 KB Unexpected end of file - int32 expected
5 Incorrect 781 ms 90732 KB Unexpected end of file - int32 expected
6 Incorrect 768 ms 90732 KB Unexpected end of file - int32 expected
7 Incorrect 800 ms 90732 KB Unexpected end of file - int32 expected
8 Incorrect 777 ms 90732 KB Unexpected end of file - int32 expected
9 Incorrect 725 ms 81492 KB Unexpected end of file - int32 expected
10 Incorrect 369 ms 46044 KB Unexpected end of file - int32 expected
11 Incorrect 510 ms 60636 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 14 ms 23788 KB Unexpected end of file - int32 expected