oj.uz

Submission #68700

# Submission time Handle Problem Language Result Execution time Memory
68700 2018-08-18T08:29:37 Z istlemin Zalmoxis (BOI18_zalmoxis) C++14
65 / 100
 345 ms 36724 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(it,*it);
			}
		}
		inserts[i].clear();
        for(auto e:newInserts)
			inserts[i].push_back(e);
    }
    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 223 ms 35892 KB Output is correct
2 Correct 226 ms 36568 KB Output is correct
3 Correct 199 ms 36568 KB Output is correct
4 Correct 223 ms 36580 KB Output is correct
5 Correct 214 ms 36604 KB Output is correct
6 Correct 192 ms 36604 KB Output is correct

Subtask #2
35.0 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 254 ms 36604 KB Unexpected end of file - int32 expected
2 Correct 223 ms 36604 KB Output is correct
3 Correct 210 ms 36700 KB Output is correct
4 Correct 210 ms 36724 KB Output is correct
5 Correct 257 ms 36724 KB Output is correct
6 Correct 198 ms 36724 KB Output is correct
7 Incorrect 208 ms 36724 KB Unexpected end of file - int32 expected
8 Incorrect 345 ms 36724 KB Unexpected end of file - int32 expected
9 Correct 223 ms 36724 KB Output is correct
10 Incorrect 163 ms 36724 KB Unexpected end of file - int32 expected
11 Correct 226 ms 36724 KB Output is correct
12 Incorrect 2 ms 36724 KB Unexpected end of file - int32 expected
13 Incorrect 3 ms 36724 KB Unexpected end of file - int32 expected
14 Incorrect 2 ms 36724 KB Unexpected end of file - int32 expected