oj.uz

Submission #654104

# Submission time Handle Problem Language Result Execution time Memory
654104 2022-10-30T00:08:54 Z sofija6 Zalmoxis (BOI18_zalmoxis) C++14
30 / 100
 1000 ms 262144 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=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++)
        {
            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++;
            }
            for (ll k=pos;k<v.size();k++)
                cout << v[k] << " ";
        }
    }
    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:62: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]
   62 |             for (ll k=pos;k<v.size();k++)
      |                           ~^~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 548 ms 57420 KB Output is correct
2 Correct 595 ms 57368 KB Output is correct
3 Correct 555 ms 57448 KB Output is correct
4 Correct 592 ms 57444 KB Output is correct
5 Correct 562 ms 57428 KB Output is correct
6 Correct 535 ms 57440 KB Output is correct

Subtask #2
0 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 808 ms 110012 KB Expected EOF
2 Incorrect 668 ms 63772 KB Expected EOF
3 Incorrect 645 ms 63916 KB Expected EOF
4 Execution timed out 1073 ms 138784 KB Time limit exceeded
5 Incorrect 672 ms 91720 KB Expected EOF
6 Incorrect 798 ms 112816 KB Expected EOF
7 Incorrect 896 ms 148592 KB Expected EOF
8 Incorrect 568 ms 74892 KB Expected EOF
9 Execution timed out 1072 ms 90144 KB Time limit exceeded
10 Execution timed out 1079 ms 80888 KB Time limit exceeded
11 Execution timed out 1061 ms 84000 KB Time limit exceeded
12 Runtime error 277 ms 262144 KB Execution killed with signal 9
13 Runtime error 248 ms 262144 KB Execution killed with signal 9
14 Runtime error 261 ms 262144 KB Execution killed with signal 9