This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
const int N = 5e6 + 5;
int n, k, arr[N];
vector<int> nums[N];
vector<pair<int, int>> v, vnext;
vector<int> vec, ans;
bool isneeded[N];
int main(){
ios_base::sync_with_stdio(false);cin.tie(NULL);
cin >> n >> k;
for(int i = 0; i < n; i++){
cin >> arr[i];
nums[i].push_back(arr[i]);
v.push_back({arr[i], i});
}
for(int cur = 1; cur <= 29; cur++){
reverse(v.begin(), v.end());
while(!v.empty()){
pair<int, int> p = v.back(); v.pop_back();
if(p.first != cur) vnext.push_back(p);
else{
if(!v.empty() && v.back().first == cur){
vnext.push_back({cur + 1, v.back().second});
v.pop_back();
}
else{
nums[p.second].push_back(cur);
vnext.push_back({cur + 1, p.second});
}
}
}
swap(v, vnext);
vnext.clear();
}
for(int i = 0; i < n; i++){
for(auto x : nums[i]) vec.push_back(x);
if(vec.size() >= N) return 31;
}
int ptr = 0;
for(int i = 0; i < vec.size(); i++){
if(ptr < n && vec[ptr] == arr[i]) isneeded[i] = true, ptr++;
}
for(int i = 0; i < vec.size(); i++){
if(isneeded[i]) ans.push_back(vec[i]);
else{
vector<int> stk;
stk.push_back(vec[i]);
while(!stk.empty() && ans.size() + (vec.size() - i - 1) + stk.size() < n + k){
int cur = stk.back(); stk.pop_back();
if(cur == 1) ans.push_back(1);
else stk.push_back(cur - 1), stk.push_back(cur - 1);
}
while(!stk.empty()){
ans.push_back(stk.back());
stk.pop_back();
}
}
}
for(auto x : ans) cout << x << " ";
cout << "\n";
}
Compilation message (stderr)
zalmoxis.cpp: In function 'int main()':
zalmoxis.cpp:61:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
61 | for(int i = 0; i < vec.size(); i++){
| ~~^~~~~~~~~~~~
zalmoxis.cpp:65:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
65 | for(int i = 0; i < vec.size(); i++){
| ~~^~~~~~~~~~~~
zalmoxis.cpp:72:73: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
72 | while(!stk.empty() && ans.size() + (vec.size() - i - 1) + stk.size() < n + k){
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |