Submission #68722

#TimeUsernameProblemLanguageResultExecution timeMemory
68722istleminZalmoxis (BOI18_zalmoxis)C++14
70 / 100
300 ms76940 KiB
#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; }*/ }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...