oj.uz

Submission #654102

# Submission time Handle Problem Language Result Execution time Memory
654102 2022-10-30T00:03:18 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;
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++)
        {
            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 806 ms 111880 KB Output is correct
2 Correct 775 ms 111912 KB Output is correct
3 Correct 782 ms 111916 KB Output is correct
4 Correct 825 ms 112016 KB Output is correct
5 Correct 815 ms 112016 KB Output is correct
6 Correct 791 ms 111976 KB Output is correct

Subtask #2
0 / 70.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1092 ms 135752 KB Time limit exceeded
2 Incorrect 788 ms 117996 KB Expected EOF
3 Incorrect 800 ms 114276 KB Expected EOF
4 Execution timed out 1100 ms 186124 KB Time limit exceeded
5 Incorrect 874 ms 117092 KB Expected EOF
6 Execution timed out 1060 ms 167528 KB Time limit exceeded
7 Execution timed out 1083 ms 203008 KB Time limit exceeded
8 Incorrect 824 ms 113340 KB Expected EOF
9 Execution timed out 1096 ms 74896 KB Time limit exceeded
10 Execution timed out 1090 ms 64680 KB Time limit exceeded
11 Execution timed out 1089 ms 68644 KB Time limit exceeded
12 Runtime error 264 ms 262144 KB Execution killed with signal 9
13 Runtime error 267 ms 262144 KB Execution killed with signal 9
14 Runtime error 266 ms 262144 KB Execution killed with signal 9