Submission #944333

#	Time	Username	Problem	Language	Result	Execution time	Memory
944333		rolandpetrean	Zalmoxis (BOI18_zalmoxis)	C++17	100 / 100	134 ms	36240 KiB

zalmoxis

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

using ll = long long;
//#define int ll

#define endl '\n'
#define pb push_back
using pi = array<int, 2>;
template<class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }

int32_t main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  
  //ifstream cin("zalmoxis.in");
  //ofstream cout("zalmoxis.out");
  
  int n, k;
  cin >> n >> k;
  
  vector<int> a(n);
  for (int i = 0; i < n; ++i) cin >> a[i];
    
  vector<pi> st;
  auto process = [&]() {
    while (st.size() >= 2 && st.back()[0] == st.end()[-2][0]) {
      int x = st.back()[0], idx = st.back()[1];
      st.pop_back();
      st.pop_back();
      st.pb({x + 1, idx});
    }
  };
  
  vector<vector<int>> in_after(n);
  for (int i = 0; i < n; ++i) {
    while (!st.empty() && a[i] > st.back()[0]) {
      int x = st.back()[0], idx = st.back()[1];
      in_after[idx].pb(x);
      st.pb({x, idx});
      process();
    }
    st.pb({a[i], i});
    process();
  }
  while (!st.empty() && st.back()[0] != 30) {
    int x = st.back()[0], idx = st.back()[1];
    in_after[idx].pb(x);
    st.pb({x, idx});
    process();
  }
  
  for (int i = 0; i < n; ++i) k -= in_after[i].size();
  
  vector<int> ans;
  function<void(int)> split = [&](int x) {
    if (k == 0 || x == 0) {
      ans.pb(x);
      return;
    }
    --k;
    split(x - 1);
    split(x - 1);
  };
  for (int i = 0; i < n; ++i) {
    ans.pb(a[i]);
    for (int x : in_after[i]) split(x);
  }
  
  for (int x : ans) cout << x << " ";
}

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