oj.uz

Submission #654043

# Submission time Handle Problem Language Result Execution time Memory
654043 2022-10-29T16:00:27 Z Vovamatrix Zalmoxis (BOI18_zalmoxis) C++14
100 / 100
 166 ms 28188 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define PI acos(-1)
#define LSB(i) ((i) & -(i))
#define ll long long
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define fi first
#define sc second
#define th third
#define fo fourth
#define pii pair<int,int>
#define pll pair<ll,ll>
#define ldb double
#define MOD 1000000007
#define endl "\n"

#define all(data)       data.begin(),data.end()
#define TYPEMAX(type)   std::numeric_limits<type>::max()
#define TYPEMIN(type)   std::numeric_limits<type>::min()
#define ima_li_te(D,d)  find(all(D),d)
#define MAXN 1000007
ll a[MAXN];
stack<ll> s;
vector<pll> v;
int main()
{
    ios::sync_with_stdio(false); cin.tie(0);
    ll n,k; cin>>n>>k;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++)
    {
        ll x=a[i];
        while(!s.empty() && s.top()<x)
        {
            ll y=s.top(); v.pb(mp(y,1)); k--;
            while(!s.empty() && s.top()==y)
            {
                s.pop();
                y++;
            }
            s.push(y);
        }
        v.pb(mp(x,0));
        while(!s.empty() && s.top()==x)
        {
            s.pop();
            x++;
        }
        s.push(x);
    }
    while(!s.empty() && s.top()<30)
    {
        ll y=s.top(); v.pb(mp(y,1)); k--;
        while(!s.empty() && s.top()==y)
        {
            s.pop();
            y++;
        }
        s.push(y);
    }
    for(auto x:v)
    {
        if(x.sc==1)
        {
            while(!s.empty()) s.pop();
            s.push(x.fi);
            while(!s.empty() && k>0)
            {
                ll y=s.top(); s.pop();
                if(y==0) cout<<0<<" ";
                else
                {
                    s.push(y-1);
                    s.push(y-1);
                    k--;
                }
            }
            while(!s.empty())
            {
                cout<<s.top()<<" ";
                s.pop ();
            }
        }
        else cout<<x.fi<<" ";
    }
    return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 128 ms 28084 KB Output is correct
2 Correct 134 ms 28008 KB Output is correct
3 Correct 129 ms 28052 KB Output is correct
4 Correct 128 ms 28160 KB Output is correct
5 Correct 127 ms 27992 KB Output is correct
6 Correct 135 ms 27984 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 130 ms 28044 KB Output is correct
2 Correct 166 ms 28008 KB Output is correct
3 Correct 137 ms 28052 KB Output is correct
4 Correct 129 ms 28156 KB Output is correct
5 Correct 134 ms 28068 KB Output is correct
6 Correct 128 ms 28040 KB Output is correct
7 Correct 124 ms 28080 KB Output is correct
8 Correct 124 ms 28188 KB Output is correct
9 Correct 134 ms 24956 KB Output is correct
10 Correct 126 ms 12204 KB Output is correct
11 Correct 113 ms 21780 KB Output is correct
12 Correct 89 ms 2252 KB Output is correct
13 Correct 81 ms 2280 KB Output is correct
14 Correct 83 ms 2324 KB Output is correct