Submission #750432

#	Time	Username	Problem	Language	Result	Execution time	Memory
750432		emad234	Zalmoxis (BOI18_zalmoxis)	C++17	0 / 100	273 ms	18724 KiB

zalmoxis

#include <bits/stdc++.h>
#define all(v) ((v).begin(),(v).end())
typedef long long ll;
using namespace std;
const ll mod = 1e9 + 7;
const ll mxN = 4e6 + 5;
int a[mxN];
stack<int>st;
deque<pair<int,int>>dq;
vector<pair<int,int>>v;
signed main() {
  // ios_base::sync_with_stdio(0);
  // cin.tie(0);cout.tie(0);
  int n,k;
  cin >>n>>k;
  for(int i = 0 ;i < n;i++){
    cin >>a[i];
  }
  st.push(a[0]);
  for(int i = 1;i < n;i++){
    int u = st.top();
    while(u < a[i]){
      // cout<<u<<' '<<i - 1<<'\n';
      dq.push_back({u,i - 1});
      u++;

      st.pop();
      if(st.size() && st.top() == u){
        st.pop();
        u++;
      }
      st.push(u);
    }
    u = a[i];
    while(st.size() && u == st.top()){
      u++;
      st.pop();
    }
    st.push(u);
  }
  while(st.size()){
    int u = st.top();
    if(u == 30) break;
    // cout<<u<<'\n';
    st.pop();
    u++;
    dq.push_front({u,n - 1});
    if(st.size() && st.top() == u){
      st.pop();
      u++;
    }
    st.push(u);
  }
  int rm = dq.size();
  while(dq.size()){
    while(dq.front().first != 0 && rm < k){
      pair<int,int> u = dq.front();
      dq.pop_front();
      dq.push_front({u.first - 1,u.second});
      dq.push_front({u.first - 1,u.second});
      rm++;
    }
    v.push_back(dq.front());
    dq.pop_front();
  }
  int idx = 0;
  for(int i = 0;i < n;i++){
    cout<<a[i]<<' ';
    while(v[idx].second == i){
      cout<<v[idx].first<<' ';
      idx++;
    }
  }
}

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