oj.uz

Submission #68701

# Submission time Handle Problem Language Result Execution time Memory
68701 2018-08-18T08:31:05 Z istlemin Zalmoxis (BOI18_zalmoxis) C++14
65 / 100
 320 ms 65616 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);
    }
    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 203 ms 33788 KB Output is correct
2 Correct 207 ms 33912 KB Output is correct
3 Correct 233 ms 33912 KB Output is correct
4 Correct 291 ms 33984 KB Output is correct
5 Correct 226 ms 33984 KB Output is correct
6 Correct 210 ms 33996 KB Output is correct

Subtask #2
35.0 / 70.0

# Verdict Execution time Memory Grader output
1 Runtime error 169 ms 63460 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Correct 211 ms 65432 KB Output is correct
3 Correct 278 ms 65560 KB Output is correct
4 Correct 263 ms 65600 KB Output is correct
5 Correct 251 ms 65600 KB Output is correct
6 Correct 249 ms 65616 KB Output is correct
7 Runtime error 224 ms 65616 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 187 ms 65616 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Correct 256 ms 65616 KB Output is correct
10 Runtime error 129 ms 65616 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Correct 320 ms 65616 KB Output is correct
12 Runtime error 6 ms 65616 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Runtime error 4 ms 65616 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Runtime error 4 ms 65616 KB Execution killed with signal 11 (could be triggered by violating memory limits)