oj.uz

Submission #654106

# Submission time Handle Problem Language Result Execution time Memory
654106 2022-10-30T00:25:05 Z sofija6 Zalmoxis (BOI18_zalmoxis) C++14
100 / 100
 582 ms 57392 KB 
#include <bits/stdc++.h>
#define ll long long
#define MAXN 1000010
using namespace std;
vector<ll> m[MAXN];
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);
    }
    if (x!=30)
    {
        for (ll i=x;i<30;i++)
        {
            k--;
            m[n].push_back(i);
        }
    }
    for (ll i=1;i<=n;i++)
    {
        cout << a[i] << " ";
        for (ll j=0;j<m[i].size();j++)
        {
            vector<ll> v;
            v.push_back(m[i][j]);
            ll pos=0;
            while (k && v[pos])
            {
                v.push_back(v[pos]-1);
                v.push_back(v[pos]-1);
                pos++;
                k--;
            }
            for (ll l=pos;l<v.size();l++)
                cout << v[l] << " ";
        }
    }
    return 0;
}

Compilation message

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

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 530 ms 57332 KB Output is correct
2 Correct 548 ms 57256 KB Output is correct
3 Correct 558 ms 57288 KB Output is correct
4 Correct 557 ms 57348 KB Output is correct
5 Correct 521 ms 57292 KB Output is correct
6 Correct 527 ms 57312 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 550 ms 57288 KB Output is correct
2 Correct 539 ms 57192 KB Output is correct
3 Correct 582 ms 57348 KB Output is correct
4 Correct 541 ms 57292 KB Output is correct
5 Correct 538 ms 57392 KB Output is correct
6 Correct 517 ms 57348 KB Output is correct
7 Correct 528 ms 57328 KB Output is correct
8 Correct 520 ms 57344 KB Output is correct
9 Correct 508 ms 55420 KB Output is correct
10 Correct 244 ms 44572 KB Output is correct
11 Correct 348 ms 48924 KB Output is correct
12 Correct 80 ms 37100 KB Output is correct
13 Correct 77 ms 37176 KB Output is correct
14 Correct 81 ms 37128 KB Output is correct