oj.uz

Submission #68708

# Submission time Handle Problem Language Result Execution time Memory
68708 2018-08-18T08:46:56 Z istlemin Zalmoxis (BOI18_zalmoxis) C++14
70 / 100
 300 ms 42860 KB 
#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;

int main(){
	cin.sync_with_stdio(false);
	ll START = 30;
    ll n,k;
    cin>>n>>k;
    vi z(n);
    rep(i,0,n) cin>>z[i];
	/*vi z = {START};
    rep(i,0,n+k-1){
		ll rIndex = rand()%z.size();
        ll rVal = z[rIndex];
        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;*/



    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]++;
		}
	}
	//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);
    rep(i,0,n){
        cout<<z[i]<<" ";
		rep(j,0,inserts[i].size()) cout<<inserts[i][j]<<" ";
    }
    cout<<endl;

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

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 214 ms 33784 KB Output is correct
2 Correct 300 ms 34000 KB Output is correct
3 Correct 248 ms 34000 KB Output is correct
4 Correct 248 ms 34000 KB Output is correct
5 Correct 232 ms 34000 KB Output is correct
6 Correct 232 ms 34000 KB Output is correct

Subtask #2
40.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 261 ms 34000 KB Output is correct
2 Correct 220 ms 34000 KB Output is correct
3 Correct 223 ms 34000 KB Output is correct
4 Correct 202 ms 34012 KB Output is correct
5 Correct 225 ms 34012 KB Output is correct
6 Correct 215 ms 34012 KB Output is correct
7 Correct 237 ms 34016 KB Output is correct
8 Correct 239 ms 34040 KB Output is correct
9 Incorrect 247 ms 34244 KB not a zalsequence
10 Incorrect 187 ms 38856 KB not a zalsequence
11 Incorrect 197 ms 38856 KB not a zalsequence
12 Incorrect 165 ms 42860 KB not a zalsequence
13 Incorrect 202 ms 42860 KB not a zalsequence
14 Incorrect 170 ms 42860 KB not a zalsequence