Submission #654106

#	Time	Username	Problem	Language	Result	Execution time	Memory
654106		sofija6	Zalmoxis (BOI18_zalmoxis)	C++14	100 / 100	582 ms	57392 KiB

zalmoxis

#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 (stderr)

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 / 30
• Subtask 2: 70 / 70