oj.uz

Submission #155379

# Submission time Handle Problem Language Result Execution time Memory
155379 2019-09-27T17:15:26 Z Charis02 Zalmoxis (BOI18_zalmoxis) C++14
100 / 100
 890 ms 108280 KB 
#include<iostream>
#include<stdio.h>
#include<vector>
#include<cmath>
#include<queue>
#include<string.h>
#include<map>
#include<set>
#include<algorithm>
#define ll int
#define pi pair < ll,ll >
#define mp(a,b) make_pair(a,b)
#define rep(i,a,b) for(int i = a;i < b;i++)
#define N 2000004
#define INF 1e9+7

using namespace std;

ll n,k,ar[N],orig[N];
set < pi > s;
ll epomeno[N];
vector < pi > res;

void solve()
{
    if((*s.begin()).first == 30)
        return;

    set < pi >::iterator it = s.begin();
    pi cur = *it;
    swap(cur.first,cur.second);

    if(epomeno[cur.first] < n && ar[epomeno[cur.first]] == cur.second)
    {
        epomeno[cur.first] = epomeno[epomeno[cur.first]];
        s.erase(s.begin());
    }
    else
        res.push_back(cur);

    s.erase(s.begin());
    s.insert(mp(cur.second+1,cur.first));
    ar[cur.first]++;

    solve();

    return;
}

bool cmp(const pi &a,const pi &b)
{
    if(a.first == b.first)
        return a.second > b.second;

    return a.first < b.first;
}

int main()
{
    ios_base::sync_with_stdio(false);

    cin >> n >> k;

    rep(i,0,n)
    {
        cin >> ar[i];
        orig[i] = ar[i];
        epomeno[i] = i+1;
        s.insert(mp(ar[i],i));
    }

    solve();

    ll cur = 0;
    ll sz = res.size();
    ll start = 0;

    while(sz < k)
    {
        if(res[start].second == 0)
        {
            start++;
            continue;
        }

        res[start].second--;
        res.push_back(res[start]);

        sz++;
    }

    sort(res.begin(),res.end(),cmp);

    rep(i,0,n)
    {
        while(cur < k && res[cur].first <= i)
        {
            cout << res[cur].second << " ";
            cur++;
        }

        cout << orig[i] << " ";
    }

    cout << endl;

    return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 805 ms 108280 KB Output is correct
2 Correct 796 ms 108152 KB Output is correct
3 Correct 789 ms 108088 KB Output is correct
4 Correct 785 ms 108192 KB Output is correct
5 Correct 784 ms 108152 KB Output is correct
6 Correct 821 ms 108148 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 890 ms 108220 KB Output is correct
2 Correct 841 ms 108048 KB Output is correct
3 Correct 809 ms 108200 KB Output is correct
4 Correct 888 ms 108244 KB Output is correct
5 Correct 858 ms 108192 KB Output is correct
6 Correct 858 ms 108280 KB Output is correct
7 Correct 877 ms 108088 KB Output is correct
8 Correct 851 ms 108252 KB Output is correct
9 Correct 757 ms 95040 KB Output is correct
10 Correct 429 ms 40528 KB Output is correct
11 Correct 564 ms 62992 KB Output is correct
12 Correct 171 ms 10340 KB Output is correct
13 Correct 163 ms 10456 KB Output is correct
14 Correct 163 ms 10376 KB Output is correct