oj.uz

Submission #68725

# Submission time Handle Problem Language Result Execution time Memory
68725 2018-08-18T09:16:00 Z istlemin Zalmoxis (BOI18_zalmoxis) C++14
70 / 100
 290 ms 45540 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;

    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){
        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);

    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 233 ms 41768 KB Output is correct
2 Correct 262 ms 41972 KB Output is correct
3 Correct 254 ms 41972 KB Output is correct
4 Correct 264 ms 41972 KB Output is correct
5 Correct 258 ms 41972 KB Output is correct
6 Correct 219 ms 41972 KB Output is correct

Subtask #2
40.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 246 ms 41972 KB Output is correct
2 Correct 235 ms 41972 KB Output is correct
3 Correct 234 ms 41972 KB Output is correct
4 Correct 229 ms 41972 KB Output is correct
5 Correct 232 ms 42000 KB Output is correct
6 Correct 290 ms 42000 KB Output is correct
7 Correct 268 ms 42060 KB Output is correct
8 Correct 275 ms 42060 KB Output is correct
9 Incorrect 277 ms 42340 KB not a zalsequence
10 Incorrect 225 ms 42340 KB not a zalsequence
11 Incorrect 252 ms 45540 KB not a zalsequence
12 Incorrect 165 ms 45540 KB not a zalsequence
13 Incorrect 153 ms 45540 KB not a zalsequence
14 Incorrect 158 ms 45540 KB not a zalsequence