Submission #68722

#	Time	Username	Problem	Language	Result	Execution time	Memory
68722		istlemin	Zalmoxis (BOI18_zalmoxis)	C++14	70 / 100	300 ms	76940 KiB

zalmoxis

#include<bits/stdc++.h>

using namespace std;

#define rep(i,a,b) for(int i = a; i<int(b);++i)
#define all(v) v.begin(),v.end()
#define sz(v) v.size()
#define trav(a,c) for(auto a: c)

typedef long long ll;
typedef vector<ll> vi;
typedef pair<ll,ll> pii;

bool isZen(vi &z){
	vi s;
    s.push_back(z[0]);
    rep(i,1,z.size()){
        if(z[i]>s[s.size()-1]){
			return false;
        }
		s.push_back(z[i]);
		while(s.size()>=2&&s[s.size()-2]==s[s.size()-1]){
			s.pop_back();
			s[s.size()-1]++;
		}
    }
    if(s.size()!=1||s[0]!=30) return false;
    return true;
}

int main(int argc,char* argv[]){
	cin.sync_with_stdio(false);
	ll START = 30;
    ll n,k;
    cin>>n>>k;
    vi z(n);
    rep(i,0,n) cin>>z[i];

    /*srand(atoi(argv[1]));
    n = rand()%100+1;
    k = rand()%100+1;
	vi z = {START};
    rep(i,0,n+k-1){
		ll rIndex = rand()%z.size();
        ll rVal = z[rIndex];
        if(rVal<=0){
			i--;
			continue;
        }
        z.erase(z.begin()+rIndex);
        z.insert(z.begin()+rIndex,rVal-1);
        z.insert(z.begin()+rIndex,rVal-1);
    }
    //rep(i,0,z.size()) cout<<z[i]<<" ";
    //cout<<endl;

    rep(i,0,k){
		z.erase(z.begin()+rand()%z.size());
    }*/

    /*rep(i,0,z.size()) cout<<z[i]<<" ";
    cout<<endl;
    cout<<endl;
    cout<<endl;
	*/


    vi s;
    s.push_back(z[0]);
    vector<vi> inserts(n);
    rep(i,1,n){
        while(z[i]>s[s.size()-1]){
            inserts[i-1].push_back(s[s.size()-1]);
			--k;
			s[s.size()-1]++;
			while(s.size()>=2&&s[s.size()-2]==s[s.size()-1]){
				s.pop_back();
				s[s.size()-1]++;
			}
        }
		s.push_back(z[i]);
		while(s.size()>=2&&s[s.size()-2]==s[s.size()-1]){
			s.pop_back();
			s[s.size()-1]++;
		}
    }
	while(s[0]!=START){
		inserts[n-1].push_back(s[s.size()-1]);
		--k;
		s[s.size()-1]++;
		while(s.size()>=2&&s[s.size()-2]==s[s.size()-1]){
			s.pop_back();
			s[s.size()-1]++;
		}
	}
    /*rep(i,0,n){
        cout<<z[i]<<" ";
		rep(j,0,inserts[i].size()) {
			cout<<inserts[i][j]<<" ";
		}
    }
    cout<<endl;
    cout<<endl;*/
	//k+=10;
    rep(i,0,n){
        list<ll> newInserts;
        list<ll>::iterator it = newInserts.end();
        rep(j,0,inserts[i].size()){
            if(it == newInserts.end()){
				newInserts.push_back(inserts[i][j]);
                it = prev(newInserts.end());
			}else{
				newInserts.push_back(inserts[i][j]);
			}
			while(k&&*it>0){
				--k;
				(*it)--;
				newInserts.insert(next(it),*it);
				while(it!=newInserts.end()&&(*it)==0)
					++it;
			}
		}
		inserts[i].clear();
        for(auto e:newInserts)
			inserts[i].push_back(e);
    }
    //if(k!=0){
		//rep(i,0,n)
			//rep(j,0,inserts[i].size())
				//assert(inserts[i][j]>=0);
    //}
    assert(k==0);
    vi ans;
    rep(i,0,n){
        cout<<z[i]<<" ";
        ans.push_back(z[i]);
		rep(j,0,inserts[i].size()) {
			ans.push_back(inserts[i][j]);
			cout<<inserts[i][j]<<" ";
		}
    }
    //cout<<endl;
   // cout<<endl;

    assert(isZen(ans));


	/*cout<<endl;
    rep(i,0,n) {
		cout<<i<<":";
		rep(j,0,inserts[i].size()) cout<<inserts[i][j]<<" ";
		cout<<endl;
    }*/
}

• Subtask 1: 30 / 30
• Subtask 2: 40 / 70