Submission #572444

#	Time	Username	Problem	Language	Result	Execution time	Memory
572444		urosk	Zalmoxis (BOI18_zalmoxis)	C++14	100 / 100	138 ms	28168 KiB

zalmoxis

#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 / 30
• Subtask 2: 70 / 70