oj.uz

Submission #155378

# Submission time Handle Problem Language Result Execution time Memory
155378 2019-09-27T17:13:30 Z Charis02 Zalmoxis (BOI18_zalmoxis) C++14
85 / 100
 1000 ms 108380 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;
}

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

    rep(i,0,res.size())
        res[i].second*=-1;

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

    rep(i,0,res.size())
        res[i].second*=-1;

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

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

    cout << endl;

    return 0;
}

Compilation message

zalmoxis.cpp: In function 'int main()':
zalmoxis.cpp:13:36: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define rep(i,a,b) for(int i = a;i < b;i++)
zalmoxis.cpp:84:9:
     rep(i,0,res.size())
         ~~~~~~~~~~~~~~              
zalmoxis.cpp:84:5: note: in expansion of macro 'rep'
     rep(i,0,res.size())
     ^~~
zalmoxis.cpp:13:36: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define rep(i,a,b) for(int i = a;i < b;i++)
zalmoxis.cpp:89:9:
     rep(i,0,res.size())
         ~~~~~~~~~~~~~~              
zalmoxis.cpp:89:5: note: in expansion of macro 'rep'
     rep(i,0,res.size())
     ^~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 785 ms 108244 KB Output is correct
2 Correct 871 ms 108144 KB Output is correct
3 Correct 825 ms 108236 KB Output is correct
4 Correct 934 ms 108380 KB Output is correct
5 Correct 829 ms 108292 KB Output is correct
6 Correct 871 ms 108244 KB Output is correct

Subtask #2
55.0 / 70.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1000 ms 108300 KB Time limit exceeded
2 Correct 964 ms 108048 KB Output is correct
3 Correct 836 ms 108140 KB Output is correct
4 Execution timed out 1067 ms 107808 KB Time limit exceeded
5 Correct 985 ms 108200 KB Output is correct
6 Correct 949 ms 108224 KB Output is correct
7 Execution timed out 1012 ms 108304 KB Time limit exceeded
8 Correct 894 ms 108272 KB Output is correct
9 Correct 865 ms 94952 KB Output is correct
10 Correct 435 ms 40536 KB Output is correct
11 Correct 607 ms 63080 KB Output is correct
12 Correct 140 ms 10324 KB Output is correct
13 Correct 132 ms 10324 KB Output is correct
14 Correct 131 ms 10396 KB Output is correct