Submission #1090771

#	Time	Username	Problem	Language	Result	Execution time	Memory
1090771		noyancanturk	Zalmoxis (BOI18_zalmoxis)	C++17	100 / 100	176 ms	18248 KiB

zalmoxis

#include<bits/stdc++.h>
using namespace std;
#define pb push_back

int main(){
  #ifdef Local
    freopen(".in","r",stdin);
    freopen(".out","w",stdout);
  #endif
  int n,k;
  cin>>n>>k;
  int s[n];
  for(int i=0;i<n;i++)cin>>s[i];
  vector<int>have;
  vector<int>ans;
  vector<int>mine;
  have.pb(s[0]);
  ans.pb(s[0]);
  mine.pb(0);
  for(int i=1;i<n;i++){
    int cur=have.back();
    have.pop_back();
    while(cur<s[i]){
      ans.pb(cur);
      mine.pb(1);
      k--;
      cur++;
      while(have.size()&&cur==have.back()){
        have.pop_back();
        cur++;
      }
    }
    ans.pb(s[i]);
    mine.pb(0);
    if(cur==s[i]){
      cur++;
      while(have.size()&&have.back()==cur){
        cur++;
        have.pop_back();
      }
      have.pb(cur);
    }else{
      have.pb(cur);
      have.pb(s[i]);
    }
  }
  while(have.back()<30){
    int val=have.back();
    ans.push_back(val);
    mine.push_back(1);
    k--;
    have.pop_back();
    val++;
    while(have.size()&&val==have.back()){
      have.pop_back();
      val++;
    }
    have.pb(val);
  }
  vector<int>realans;
  for(int i=0;i<ans.size();i++){
    if(!mine[i]){
      realans.pb(ans[i]);
    }else{
      vector<int>gotten;
      gotten.pb(ans[i]);
      while(k&&gotten.size()){
        if(gotten.back()==1){
          realans.pb(gotten.back());
          gotten.pop_back();
        }else{
          int val=gotten.back();
          gotten.pop_back();
          gotten.pb(val-1);
          gotten.pb(val-1);
          k--;
        }
      }
      while(gotten.size()){
        realans.pb(gotten.back());
        gotten.pop_back();
      }
    }
  }
  for(int i:realans)cout<<i<<" ";
}

Compilation message (stderr)

zalmoxis.cpp: In function 'int main()':
zalmoxis.cpp:61:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |   for(int i=0;i<ans.size();i++){
      |               ~^~~~~~~~~~~

• Subtask 1: 30 / 30
• Subtask 2: 70 / 70