oj.uz

Submission #68726

# Submission time Handle Problem Language Result Execution time Memory
68726 2018-08-18T09:23:23 Z istlemin Zalmoxis (BOI18_zalmoxis) C++14
100 / 100
 358 ms 42136 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){
        vi s1;
        vi s2 = inserts[i];
        reverse(all(s2));
        while(k){
            if(s1.size()==0||s1[s1.size()-1]==0){
                if(s2.size()==0) break;
				s1.push_back(s2[s2.size()-1]);
                s2.pop_back();
            }
            if(s1[s1.size()-1]>0){
				s1[s1.size()-1]--;
                s2.push_back(s1[s1.size()-1]);
                --k;
            }
		}
		while(s2.size()){
			s1.push_back(s2[s2.size()-1]);
			s2.pop_back();
		}
		inserts[i] = s1;
        /*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);*/
    }
    assert(k==0);
    vi ans;
    rep(i,0,n){
        ans.push_back(z[i]);
		rep(j,0,inserts[i].size()) {
			ans.push_back(inserts[i][j]);
		}
    }
    assert(isZen(ans));

    rep(i,0,n){
        cout<<z[i]<<" ";
		rep(j,0,inserts[i].size()) {
			cout<<inserts[i][j]<<" ";
		}
    }
    //if(k!=0){
		//rep(i,0,n)
			//rep(j,0,inserts[i].size())
				//assert(inserts[i][j]>=0);
    //}


	/*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 235 ms 41836 KB Output is correct
2 Correct 298 ms 41836 KB Output is correct
3 Correct 239 ms 42092 KB Output is correct
4 Correct 245 ms 42092 KB Output is correct
5 Correct 273 ms 42092 KB Output is correct
6 Correct 245 ms 42092 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 283 ms 42092 KB Output is correct
2 Correct 287 ms 42092 KB Output is correct
3 Correct 307 ms 42104 KB Output is correct
4 Correct 304 ms 42108 KB Output is correct
5 Correct 358 ms 42108 KB Output is correct
6 Correct 283 ms 42108 KB Output is correct
7 Correct 310 ms 42108 KB Output is correct
8 Correct 302 ms 42136 KB Output is correct
9 Correct 301 ms 42136 KB Output is correct
10 Correct 255 ms 42136 KB Output is correct
11 Correct 276 ms 42136 KB Output is correct
12 Correct 145 ms 42136 KB Output is correct
13 Correct 150 ms 42136 KB Output is correct
14 Correct 161 ms 42136 KB Output is correct