//
// Created by 42kangaroo on 28/10/2023.
//
#include "bits/stdc++.h"
using namespace std;
#define int long long
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n, k;
cin >> n >> k;
vector<int> a(n);
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
vector<pair<int, int>> addBef;
stack<pair<int, int>> st;
auto mergeBack = [&st]() {
while (st.size() > 1) {
auto t = st.top();
st.pop();
if (st.top().second == t.second) {
st.top().second++;
} else {
st.push(t);
break;
}
}
};
for (int i = 0; i < n; ++i) {
while (!st.empty() && st.top().second < a[i]) {
addBef.push_back(st.top());
st.push({-1, st.top().second});
mergeBack();
}
st.push({i, a[i]});
mergeBack();
}
while (!st.empty() && st.top().second < 30) {
addBef.push_back(st.top());
st.push({-1, st.top().second});
mergeBack();
}
vector<int> out;
int addInd = 0;
assert(!addBef.empty());
std::sort(addBef.begin(), addBef.end());
for (int i = 0; i < n; ++i) {
vector<int> hasTo;
while (addInd < addBef.size() && addBef[addInd].first == i) {
hasTo.push_back(addBef[addInd].second);
addInd++;
}
std::reverse(hasTo.begin(), hasTo.end());
for (int q = 0; q < hasTo.size(); ++q) {
int ks = k - addBef.size() + 1;
int p2 = 1;
for (int j = 0; j <= 30; ++j, p2 *= 2) {
if (p2 >= ks || hasTo[q] == j + 1) {
for (int l = 0; l < min(ks, p2); ++l) {
if (l < p2 - ks - 1) out.push_back(hasTo[q] - j - 1);
else out.push_back(hasTo[q] - j);
assert(hasTo[q] - j - 1 >= 0);
}
k -= max(ks, p2) - 1;
break;
}
}
}
out.push_back(a[i]);
}
for (auto e: out) {
cout << e << " ";
}
}
Compilation message
zalmoxis.cpp: In function 'int main()':
zalmoxis.cpp:53:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
53 | while (addInd < addBef.size() && addBef[addInd].first == i) {
| ~~~~~~~^~~~~~~~~~~~~~~
zalmoxis.cpp:58:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
58 | for (int q = 0; q < hasTo.size(); ++q) {
| ~~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
108 ms |
18116 KB |
Output is correct |
| 2 |
Correct |
108 ms |
18376 KB |
Output is correct |
| 3 |
Correct |
111 ms |
18104 KB |
Output is correct |
| 4 |
Correct |
107 ms |
18124 KB |
Output is correct |
| 5 |
Correct |
107 ms |
18360 KB |
Output is correct |
| 6 |
Correct |
110 ms |
18108 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
117 ms |
18220 KB |
Unexpected end of file - int32 expected |
| 2 |
Runtime error |
64 ms |
16460 KB |
Execution killed with signal 6 |
| 3 |
Runtime error |
62 ms |
16464 KB |
Execution killed with signal 6 |
| 4 |
Incorrect |
108 ms |
18360 KB |
Unexpected end of file - int32 expected |
| 5 |
Incorrect |
110 ms |
18360 KB |
Unexpected end of file - int32 expected |
| 6 |
Incorrect |
110 ms |
18132 KB |
Unexpected end of file - int32 expected |
| 7 |
Incorrect |
117 ms |
18120 KB |
Unexpected end of file - int32 expected |
| 8 |
Incorrect |
108 ms |
18372 KB |
Unexpected end of file - int32 expected |
| 9 |
Runtime error |
63 ms |
19140 KB |
Execution killed with signal 6 |
| 10 |
Incorrect |
102 ms |
15708 KB |
Unexpected end of file - int32 expected |
| 11 |
Runtime error |
44 ms |
14276 KB |
Execution killed with signal 6 |
| 12 |
Incorrect |
49 ms |
10420 KB |
Unexpected end of file - int32 expected |
| 13 |
Incorrect |
55 ms |
10220 KB |
Unexpected end of file - int32 expected |
| 14 |
Incorrect |
51 ms |
10252 KB |
Unexpected end of file - int32 expected |
