oj.uz

Submission #944333

# Submission time Handle Problem Language Result Execution time Memory
944333 2024-03-12T14:55:35 Z rolandpetrean Zalmoxis (BOI18_zalmoxis) C++17
100 / 100
 134 ms 36240 KB 
#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.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 130 ms 35888 KB Output is correct
2 Correct 124 ms 36088 KB Output is correct
3 Correct 134 ms 35820 KB Output is correct
4 Correct 128 ms 36036 KB Output is correct
5 Correct 124 ms 36236 KB Output is correct
6 Correct 122 ms 35932 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 122 ms 35820 KB Output is correct
2 Correct 123 ms 35804 KB Output is correct
3 Correct 124 ms 36024 KB Output is correct
4 Correct 124 ms 36240 KB Output is correct
5 Correct 134 ms 36036 KB Output is correct
6 Correct 123 ms 35892 KB Output is correct
7 Correct 121 ms 36040 KB Output is correct
8 Correct 120 ms 36032 KB Output is correct
9 Correct 119 ms 33492 KB Output is correct
10 Correct 89 ms 17856 KB Output is correct
11 Correct 111 ms 24820 KB Output is correct
12 Correct 61 ms 6376 KB Output is correct
13 Correct 56 ms 6396 KB Output is correct
14 Correct 55 ms 6336 KB Output is correct