#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 2000005;
vector<int> vec[maxn];
int id[maxn];
int g = 0;
pair<int,int> comb(pair<int,int> a, pair<int,int> &b) {
vec[a.second].push_back(b.second);
a.first++;
return a;
}
vector<int> res;
void dfs(int u) {
res.push_back(id[u]);
for (int v : vec[u]) dfs(v);
}
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int n, k;
cin >> n >> k;
vector<pair<int,int>> v;
vector<int> ori;
int mini = 1e9;
for (int i = 0; i < n; i++) {
int x;
cin >> x;
id[g] = x;
v.push_back({x,g});
g++;
ori.push_back(x);
mini = min(mini,x);
}
for (int i = mini; i <= 29; i++) {
vector<pair<int,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--;
pair<int,int> p = {i,g};
id[g] = i;
g++;
to[to.size()-1] = comb(to[to.size()-1], p);
to.push_back(v[j]);
}
} else {
to.push_back(v[j]);
}
}
if (to[to.size()-1].first == i) {
k--;
pair<int,int> p = {i,g};
id[g] = i;
g++;
to[to.size()-1] = comb(to[to.size()-1], p);
}
v = to;
}
assert(k>=0 && v.size() == 1 && v[0].first == 30);
dfs(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:43:27: 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]
43 | for (int j = 0; j < v.size(); j++) {
| ~~^~~~~~~~~~
zalmoxis.cpp:72: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]
72 | for (int i = 0; i < res.size(); i++) {
| ~~^~~~~~~~~~~~
zalmoxis.cpp:73: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]
73 | if (ori.size()<=i || ori[i] != res[i]) {
| ~~~~~~~~~~^~~
zalmoxis.cpp:79: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]
79 | for (int i = 0; i < res.size(); i++) {
| ~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
376 ms |
115660 KB |
Output is correct |
| 2 |
Correct |
386 ms |
115780 KB |
Output is correct |
| 3 |
Correct |
390 ms |
115856 KB |
Output is correct |
| 4 |
Correct |
407 ms |
115736 KB |
Output is correct |
| 5 |
Correct |
383 ms |
115688 KB |
Output is correct |
| 6 |
Correct |
373 ms |
115612 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
381 ms |
115700 KB |
Output is correct |
| 2 |
Correct |
372 ms |
116028 KB |
Output is correct |
| 3 |
Correct |
394 ms |
115676 KB |
Output is correct |
| 4 |
Correct |
392 ms |
115776 KB |
Output is correct |
| 5 |
Correct |
387 ms |
115640 KB |
Output is correct |
| 6 |
Correct |
381 ms |
115868 KB |
Output is correct |
| 7 |
Correct |
387 ms |
115932 KB |
Output is correct |
| 8 |
Correct |
390 ms |
115792 KB |
Output is correct |
| 9 |
Correct |
346 ms |
108440 KB |
Output is correct |
| 10 |
Correct |
221 ms |
78152 KB |
Output is correct |
| 11 |
Correct |
267 ms |
93488 KB |
Output is correct |
| 12 |
Correct |
125 ms |
55404 KB |
Output is correct |
| 13 |
Correct |
126 ms |
55276 KB |
Output is correct |
| 14 |
Correct |
128 ms |
55276 KB |
Output is correct |
