oj.uz

답안 #68723

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
68723 2018-08-18T09:13:21 Z istlemin Zalmoxis (BOI18_zalmoxis) C++14
70 / 100
 353 ms 76908 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;

bool isZen(vi &z){
	vi s;
    s.push_back(z[0]);
    rep(i,1,z.size()){
        if(z[i]>s[s.size()-1]){
			return false;
        }
		s.push_back(z[i]);
		while(s.size()>=2&&s[s.size()-2]==s[s.size()-1]){
			s.pop_back();
			s[s.size()-1]++;
		}
    }
    if(s.size()!=1||s[0]!=30) return true;
    return true;
}

int main(int argc,char* argv[]){
	cin.sync_with_stdio(false);
	ll START = 30;
    ll n,k;
    cin>>n>>k;
    vi z(n);
    rep(i,0,n) cin>>z[i];

    /*srand(atoi(argv[1]));
    n = rand()%100+1;
    k = rand()%100+1;
	vi z = {START};
    rep(i,0,n+k-1){
		ll rIndex = rand()%z.size();
        ll rVal = z[rIndex];
        if(rVal<=0){
			i--;
			continue;
        }
        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;
    cout<<endl;
    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]++;
		}
	}
    /*rep(i,0,n){
        cout<<z[i]<<" ";
		rep(j,0,inserts[i].size()) {
			cout<<inserts[i][j]<<" ";
		}
    }
    cout<<endl;
    cout<<endl;*/
	//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);
    vi ans;
    rep(i,0,n){
        cout<<z[i]<<" ";
        ans.push_back(z[i]);
		rep(j,0,inserts[i].size()) {
			ans.push_back(inserts[i][j]);
			cout<<inserts[i][j]<<" ";
		}
    }
    //cout<<endl;
   // cout<<endl;

    assert(isZen(ans));


	/*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

# 결과 실행 시간 메모리 Grader output
1 Correct 231 ms 41772 KB Output is correct
2 Correct 235 ms 41772 KB Output is correct
3 Correct 241 ms 41888 KB Output is correct
4 Correct 241 ms 41984 KB Output is correct
5 Correct 353 ms 41984 KB Output is correct
6 Correct 257 ms 41984 KB Output is correct

Subtask #2
40.0 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Correct 227 ms 41984 KB Output is correct
2 Correct 285 ms 41984 KB Output is correct
3 Correct 225 ms 41984 KB Output is correct
4 Correct 252 ms 41984 KB Output is correct
5 Correct 241 ms 41984 KB Output is correct
6 Correct 258 ms 42020 KB Output is correct
7 Correct 235 ms 42020 KB Output is correct
8 Correct 235 ms 42044 KB Output is correct
9 Runtime error 285 ms 76908 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 238 ms 76908 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Runtime error 245 ms 76908 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Runtime error 205 ms 76908 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Runtime error 198 ms 76908 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Runtime error 223 ms 76908 KB Execution killed with signal 11 (could be triggered by violating memory limits)