#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 << " ";
}
# |
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 |
# |
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 |