oj.uz

Submission #572444

# Submission time Handle Problem Language Result Execution time Memory
572444 2022-06-04T11:43:15 Z urosk Zalmoxis (BOI18_zalmoxis) C++14
100 / 100
 138 ms 28168 KB 
#define here cerr<<"===========================================\n"
#include <bits/stdc++.h>
#define ld double
#define ll long long
#define llinf 100000000000000000LL // 10^17
#define pb push_back
#define popb pop_back
#define fi first
#define sc second
#define endl '\n'
#define pll pair<ll,ll>
#define pld pair<ld,ld>
#define sz(a) (ll)(a.size())
#define all(a) a.begin(),a.end()
#define ceri(a,l,r) {for(ll i_ = l;i_<=r;i_++) cerr<<a[i_]<< " ";cerr<<endl;}
#define daj_mi_malo_vremena ios_base::sync_with_stdio(false);cerr.tie(0);cout.tie(0);cin.tie(0);

using namespace std;
#define maxn 2000005
ll n,k;
ll a[maxn];
void rastavi(ll x){
    vector<ll> v;
    v.pb(x);
    while(k&&sz(v)){
        ll x = v.back(); v.popb();
        if(x==1){
            cout<<x<< " ";
        }else{
            k--;
            v.pb(x-1);
            v.pb(x-1);
        }
    }
    while(sz(v)){
        cout<<v.back()<< " ";
        v.popb();
    }
}
int main(){
	daj_mi_malo_vremena
    cin >> n >> k;
    for(ll i = 1;i<=n;i++) cin >> a[i];
    n++;
    a[n] = 30;
    vector<ll> v;
    vector<pll> ans;
    for(ll i = 1;i<=n;i++){
        while(sz(v)&&a[i]>v.back()){
            ans.pb({v.back(),1});
            k--;
            ll x = v.back();
            while(sz(v)&&v.back()==x){
                x++;
                v.popb();
            }
            v.pb(x);
        }
        ll x = a[i];
        while(sz(v)&&v.back()==x){
            x++;
            v.popb();
        }
        v.pb(x);
        if(i<=n-1) ans.pb({a[i],0});
    }
    for(pll p : ans){
        if(p.sc==0) cout<<p.fi<< " ";
        else rastavi(p.fi);
    }
    cout<<endl;
	return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 122 ms 28164 KB Output is correct
2 Correct 125 ms 28128 KB Output is correct
3 Correct 119 ms 28084 KB Output is correct
4 Correct 121 ms 28164 KB Output is correct
5 Correct 123 ms 28056 KB Output is correct
6 Correct 123 ms 28168 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 28076 KB Output is correct
2 Correct 129 ms 28012 KB Output is correct
3 Correct 136 ms 28060 KB Output is correct
4 Correct 138 ms 28144 KB Output is correct
5 Correct 122 ms 28056 KB Output is correct
6 Correct 123 ms 28052 KB Output is correct
7 Correct 121 ms 27992 KB Output is correct
8 Correct 127 ms 28032 KB Output is correct
9 Correct 119 ms 24972 KB Output is correct
10 Correct 103 ms 22056 KB Output is correct
11 Correct 110 ms 21772 KB Output is correct
12 Correct 73 ms 16204 KB Output is correct
13 Correct 72 ms 16140 KB Output is correct
14 Correct 66 ms 2272 KB Output is correct