oj.uz

Submission #1090771

# Submission time Handle Problem Language Result Execution time Memory
1090771 2024-09-18T17:59:54 Z noyancanturk Zalmoxis (BOI18_zalmoxis) C++17
100 / 100
 176 ms 18248 KB 
#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

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.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 157 ms 18216 KB Output is correct
2 Correct 170 ms 18232 KB Output is correct
3 Correct 152 ms 18248 KB Output is correct
4 Correct 158 ms 18212 KB Output is correct
5 Correct 153 ms 18232 KB Output is correct
6 Correct 152 ms 18204 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 149 ms 18248 KB Output is correct
2 Correct 157 ms 18204 KB Output is correct
3 Correct 156 ms 18200 KB Output is correct
4 Correct 160 ms 18232 KB Output is correct
5 Correct 156 ms 18204 KB Output is correct
6 Correct 176 ms 18244 KB Output is correct
7 Correct 158 ms 18236 KB Output is correct
8 Correct 157 ms 18204 KB Output is correct
9 Correct 143 ms 16912 KB Output is correct
10 Correct 100 ms 13964 KB Output is correct
11 Correct 127 ms 13592 KB Output is correct
12 Correct 72 ms 12268 KB Output is correct
13 Correct 75 ms 12264 KB Output is correct
14 Correct 58 ms 6260 KB Output is correct