oj.uz

Submission #654105

# Submission time Handle Problem Language Result Execution time Memory
654105 2022-10-30T00:24:21 Z sofija6 Zalmoxis (BOI18_zalmoxis) C++14
100 / 100
 687 ms 57372 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 617 ms 57348 KB Output is correct
2 Correct 610 ms 57208 KB Output is correct
3 Correct 605 ms 57344 KB Output is correct
4 Correct 687 ms 57264 KB Output is correct
5 Correct 627 ms 57276 KB Output is correct
6 Correct 656 ms 57220 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 645 ms 57264 KB Output is correct
2 Correct 625 ms 57204 KB Output is correct
3 Correct 647 ms 57248 KB Output is correct
4 Correct 661 ms 57336 KB Output is correct
5 Correct 623 ms 57264 KB Output is correct
6 Correct 627 ms 57264 KB Output is correct
7 Correct 626 ms 57268 KB Output is correct
8 Correct 623 ms 57372 KB Output is correct
9 Correct 567 ms 55296 KB Output is correct
10 Correct 281 ms 44396 KB Output is correct
11 Correct 430 ms 48920 KB Output is correct
12 Correct 98 ms 37172 KB Output is correct
13 Correct 92 ms 37156 KB Output is correct
14 Correct 100 ms 37120 KB Output is correct