oj.uz

Submission #654099

# Submission time Handle Problem Language Result Execution time Memory
654099 2022-10-29T23:51:21 Z sofija6 Zalmoxis (BOI18_zalmoxis) C++14
50 / 100
 756 ms 96424 KB 
#include <bits/stdc++.h>
#define ll int
#define MAXN 1000010
using namespace std;
map<ll,vector<ll> > m;
ll a[MAXN];
int main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    ll n,k,x;
    cin >> n >> k;
    priority_queue<pair<ll,pair<ll,ll> >,vector<pair<ll,pair<ll,ll> > >,greater<pair<ll,pair<ll,ll> > > > q;
    for (ll i=1;i<=n;i++)
    {
        cin >> a[i];
        q.push({a[i],{i,i}});
    }
    while (true)
    {
        auto t=q.top();
        q.pop();
        if (q.empty())
        {
            x=t.first;
            break;
        }
        if (q.top().first!=t.first || q.top().second.first!=t.second.second+1)
        {
            m[t.second.second].push_back(t.first);
            t.first++;
            q.push(t);
            k--;
            continue;
        }
        t.second.second=q.top().second.second;
        q.pop();
        t.first++;
        q.push(t);
    }
    for (ll i=1;i<=n;i++)
    {
        cout << a[i] << " ";
        for (ll j=0;j<m[i].size();j++)
            cout << m[i][j] << " ";
    }
    if (x!=30)
    {
        priority_queue<ll> q;
        for (ll i=29;i>=x && k;i--)
        {
            k--;
            q.push(i);
        }
        while (k--)
        {
            ll t=q.top();
            q.pop();
            q.push(t-1);
            q.push(t-1);
        }
        while (!q.empty())
        {
            cout << q.top() << " ";
            q.pop();
        }
    }
    return 0;
}

Compilation message

zalmoxis.cpp: In function 'int main()':
zalmoxis.cpp:43:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |         for (ll j=0;j<m[i].size();j++)
      |                     ~^~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 701 ms 96356 KB Output is correct
2 Correct 722 ms 96228 KB Output is correct
3 Correct 736 ms 96252 KB Output is correct
4 Correct 731 ms 96268 KB Output is correct
5 Correct 748 ms 96400 KB Output is correct
6 Correct 706 ms 96328 KB Output is correct

Subtask #2
20.0 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 743 ms 96224 KB Unexpected end of file - int32 expected
2 Correct 672 ms 96168 KB Output is correct
3 Incorrect 669 ms 96304 KB Unexpected end of file - int32 expected
4 Incorrect 735 ms 96352 KB Unexpected end of file - int32 expected
5 Incorrect 756 ms 96252 KB Unexpected end of file - int32 expected
6 Incorrect 727 ms 96360 KB Unexpected end of file - int32 expected
7 Incorrect 707 ms 96320 KB Unexpected end of file - int32 expected
8 Incorrect 699 ms 96424 KB Unexpected end of file - int32 expected
9 Incorrect 616 ms 80732 KB Unexpected end of file - int32 expected
10 Correct 355 ms 39868 KB Output is correct
11 Incorrect 420 ms 52240 KB Unexpected end of file - int32 expected
12 Correct 160 ms 7440 KB Output is correct
13 Correct 163 ms 7352 KB Output is correct
14 Incorrect 161 ms 7376 KB not a zalsequence