#include <bits/stdc++.h>
#define int long long
using namespace std;
pair<int,vector<int>> comb(pair<int,vector<int>> a, pair<int,vector<int>> &b) {
for (int x : b.second) a.second.push_back(x);
a.first++;
return a;
}
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int n, k;
cin >> n >> k;
vector<pair<int,vector<int>>> v;
vector<int> ori;
int mini = 1e9;
for (int i = 0; i < n; i++) {
int x;
cin >> x;
v.push_back({x,{x}});
ori.push_back(x);
mini = min(mini,x);
}
for (int i = mini; i <= 29; i++) {
vector<pair<int,vector<int>>> to;
for (int j = 0; j < v.size(); j++) {
if (!to.empty() && to[to.size()-1].first == i) {
if (v[j].first == i) {
to[to.size()-1] = comb(to[to.size()-1], v[j]);
} else {
k--;
to[to.size()-1].first++;
to[to.size()-1].second.push_back(i);
to.push_back(v[j]);
}
} else {
to.push_back(v[j]);
}
}
if (to[to.size()-1].first == i) {
k--;
to[to.size()-1].first++;
to[to.size()-1].second.push_back(i);
}
v = to;
}
assert(k>=0 && v.size() == 1 && v[0].first == 30);
vector<int> res = v[0].second;
int mark = -1;
if (k != 0) {
for (int i = 0; i < res.size(); i++) {
if (ori.size()<=i || ori[i] != res[i]) {
mark = i;
break;
}
}
}
for (int i = 0; i < res.size(); i++) {
if (i == mark) {
for (int j = res[i]-1; j >= res[i]-k; j--) cout << j << ' ';
cout << res[i]-k << ' ';
} else {
cout << res[i] << ' ';
}
}
cout << '\n';
}
Compilation message
zalmoxis.cpp: In function 'int main()':
zalmoxis.cpp:30:27: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, std::vector<long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
30 | for (int j = 0; j < v.size(); j++) {
| ~~^~~~~~~~~~
zalmoxis.cpp:55:27: 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]
55 | for (int i = 0; i < res.size(); i++) {
| ~~^~~~~~~~~~~~
zalmoxis.cpp:56:27: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
56 | if (ori.size()<=i || ori[i] != res[i]) {
| ~~~~~~~~~~^~~
zalmoxis.cpp:62:23: 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]
62 | for (int i = 0; i < res.size(); i++) {
| ~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1097 ms |
143552 KB |
Time limit exceeded |
| 2 |
Execution timed out |
1107 ms |
145368 KB |
Time limit exceeded |
| 3 |
Execution timed out |
1093 ms |
144244 KB |
Time limit exceeded |
| 4 |
Execution timed out |
1107 ms |
144592 KB |
Time limit exceeded |
| 5 |
Execution timed out |
1096 ms |
145140 KB |
Time limit exceeded |
| 6 |
Execution timed out |
1087 ms |
142428 KB |
Time limit exceeded |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1093 ms |
144100 KB |
Time limit exceeded |
| 2 |
Execution timed out |
1101 ms |
142296 KB |
Time limit exceeded |
| 3 |
Execution timed out |
1095 ms |
144972 KB |
Time limit exceeded |
| 4 |
Execution timed out |
1099 ms |
145504 KB |
Time limit exceeded |
| 5 |
Execution timed out |
1061 ms |
144664 KB |
Time limit exceeded |
| 6 |
Execution timed out |
1100 ms |
143840 KB |
Time limit exceeded |
| 7 |
Execution timed out |
1100 ms |
145120 KB |
Time limit exceeded |
| 8 |
Execution timed out |
1096 ms |
145840 KB |
Time limit exceeded |
| 9 |
Execution timed out |
1105 ms |
119520 KB |
Time limit exceeded |
| 10 |
Correct |
535 ms |
53640 KB |
Output is correct |
| 11 |
Correct |
723 ms |
77056 KB |
Output is correct |
| 12 |
Correct |
111 ms |
8428 KB |
Output is correct |
| 13 |
Correct |
96 ms |
8300 KB |
Output is correct |
| 14 |
Correct |
95 ms |
8300 KB |
Output is correct |
