oj.uz

답안 #68704

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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)