oj.uz

Submission #68702

# Submission time Handle Problem Language Result Execution time Memory
68702 2018-08-18T08:35:47 Z istlemin Zalmoxis (BOI18_zalmoxis) C++14
65 / 100
 252 ms 65652 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);
    }
    if(k!=0){
		rep(i,0,n)
			rep(j,0,inserts[i].size())
				assert(inserts[i][j]==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 238 ms 33740 KB Output is correct
2 Correct 249 ms 33912 KB Output is correct
3 Correct 233 ms 33992 KB Output is correct
4 Correct 205 ms 33992 KB Output is correct
5 Correct 252 ms 34016 KB Output is correct
6 Correct 239 ms 34016 KB Output is correct

Subtask #2
35.0 / 70.0

# Verdict Execution time Memory Grader output
1 Runtime error 154 ms 63456 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Correct 204 ms 65432 KB Output is correct
3 Correct 229 ms 65516 KB Output is correct
4 Correct 216 ms 65652 KB Output is correct
5 Correct 209 ms 65652 KB Output is correct
6 Correct 198 ms 65652 KB Output is correct
7 Runtime error 167 ms 65652 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 177 ms 65652 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Correct 229 ms 65652 KB Output is correct
10 Runtime error 121 ms 65652 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Correct 202 ms 65652 KB Output is correct
12 Runtime error 7 ms 65652 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Runtime error 4 ms 65652 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Runtime error 3 ms 65652 KB Execution killed with signal 11 (could be triggered by violating memory limits)