oj.uz

Submission #654101

# Submission time Handle Problem Language Result Execution time Memory
654101 2022-10-29T23:58:35 Z sofija6 Zalmoxis (BOI18_zalmoxis) C++14
30 / 100
 1000 ms 194848 KB 
#include <bits/stdc++.h>
#define ll long long
#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);
    }
    if (x!=30)
    {
        for (ll i=29;i>=x;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++)
        {
            priority_queue<ll> q;
            q.push(m[i][j]);
            while (k-- && q.top())
            {
                q.push(q.top()-1);
                q.push(q.top()-1);
                q.pop();
            }
            while (!q.empty())
            {
                cout << q.top() << " ";
                q.pop();
            }
        }
    }
    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++)
      |                     ~^~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 754 ms 111904 KB Output is correct
2 Correct 788 ms 112012 KB Output is correct
3 Correct 766 ms 111968 KB Output is correct
4 Correct 774 ms 112020 KB Output is correct
5 Correct 769 ms 112040 KB Output is correct
6 Correct 778 ms 112092 KB Output is correct

Subtask #2
0 / 70.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1090 ms 82188 KB Time limit exceeded
2 Incorrect 850 ms 116876 KB Expected EOF
3 Incorrect 833 ms 114484 KB Expected EOF
4 Execution timed out 1094 ms 151020 KB Time limit exceeded
5 Execution timed out 1010 ms 116700 KB Time limit exceeded
6 Execution timed out 1102 ms 163344 KB Time limit exceeded
7 Execution timed out 1079 ms 194848 KB Time limit exceeded
8 Incorrect 838 ms 113256 KB Expected EOF
9 Execution timed out 1093 ms 60208 KB Time limit exceeded
10 Execution timed out 1075 ms 38344 KB Time limit exceeded
11 Execution timed out 1063 ms 63084 KB Time limit exceeded
12 Execution timed out 1102 ms 133940 KB Time limit exceeded
13 Execution timed out 1079 ms 133900 KB Time limit exceeded
14 Execution timed out 1098 ms 133820 KB Time limit exceeded