oj.uz

Submission #68704

# Submission time Handle Problem Language Result Execution time Memory
68704 2018-08-18T08:43:58 Z istlemin Zalmoxis (BOI18_zalmoxis) C++14
0 / 100
 1000 ms 263168 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 = 5;
    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
0 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1044 ms 263168 KB Time limit exceeded
2 Execution timed out 1025 ms 263168 KB Time limit exceeded
3 Execution timed out 1048 ms 263168 KB Time limit exceeded
4 Execution timed out 1035 ms 263168 KB Time limit exceeded
5 Execution timed out 1054 ms 263168 KB Time limit exceeded
6 Execution timed out 1032 ms 263168 KB Time limit exceeded

Subtask #2
0 / 70.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1047 ms 263168 KB Time limit exceeded
2 Execution timed out 1049 ms 263168 KB Time limit exceeded
3 Execution timed out 1048 ms 263168 KB Time limit exceeded
4 Execution timed out 1037 ms 263168 KB Time limit exceeded
5 Execution timed out 1045 ms 263168 KB Time limit exceeded
6 Execution timed out 1039 ms 263168 KB Time limit exceeded
7 Execution timed out 1040 ms 263168 KB Time limit exceeded
8 Execution timed out 1058 ms 263168 KB Time limit exceeded
9 Execution timed out 1045 ms 263168 KB Time limit exceeded
10 Execution timed out 1036 ms 263168 KB Time limit exceeded
11 Execution timed out 1048 ms 263168 KB Time limit exceeded
12 Execution timed out 1068 ms 263168 KB Time limit exceeded
13 Execution timed out 1048 ms 263168 KB Time limit exceeded
14 Runtime error 3 ms 263168 KB Execution killed with signal 11 (could be triggered by violating memory limits)