oj.uz

Submission #68722

# Submission time Handle Problem Language Result Execution time Memory
68722 2018-08-18T09:12:33 Z istlemin Zalmoxis (BOI18_zalmoxis) C++14
70 / 100
 300 ms 76940 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 false;
    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

# Verdict Execution time Memory Grader output
1 Correct 244 ms 41744 KB Output is correct
2 Correct 236 ms 41860 KB Output is correct
3 Correct 229 ms 41860 KB Output is correct
4 Correct 268 ms 42060 KB Output is correct
5 Correct 241 ms 42060 KB Output is correct
6 Correct 226 ms 42060 KB Output is correct

Subtask #2
40.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 259 ms 42060 KB Output is correct
2 Correct 257 ms 42060 KB Output is correct
3 Correct 223 ms 42060 KB Output is correct
4 Correct 272 ms 42116 KB Output is correct
5 Correct 268 ms 42116 KB Output is correct
6 Correct 236 ms 42116 KB Output is correct
7 Correct 274 ms 42116 KB Output is correct
8 Correct 300 ms 42116 KB Output is correct
9 Runtime error 249 ms 76940 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 242 ms 76940 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Runtime error 254 ms 76940 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Runtime error 234 ms 76940 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Runtime error 220 ms 76940 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Runtime error 219 ms 76940 KB Execution killed with signal 11 (could be triggered by violating memory limits)