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;
#define FOR(i,N) for(long long i = 0; (i) < (N); (i)++)
#define FORS(i,v,N) for(long long i = v; (i) < (N); (i)++)
#define FORI(i,v,N,inc) for(long long i = v; (i) < (N); (i)+=(inc))
#define NL '\n'
#define EL cout << NL
#define PRINTV(v) for(auto a:(v)) {cout << a << " ";};EL
#define PRINTVV(v) for(auto a:(v)) {PRINTV(a);}
#define STRP(p) "{" << (p).first << "," << (p).second << "}"
#define PRINTVP(v) for(auto a:(v)) {cout << STRP(a) << " ";};EL
#define PRINTVV(v) for(auto a:(v)) {PRINTV(a);}
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef pair<ll,ll> pl;
typedef vector<pl> vpl;
typedef vector<vpl> vvpl;
vl partsplit(ll num, ll t) {
vl res;
ll pow = 1;
ll val = num-1;
while (t) {
if (t % 2) {
FOR(_,pow) {
res.push_back(val);
}
}
t /= 2;
pow *= 2;
val --;
}
return res;
}
int main() {
cin.tie(0)->sync_with_stdio(0);
ll N,K;
cin >> N >> K;
vl s(N);
FOR(i,N) cin >> s[i];
vvl changes(N);
vl index(N);
vl cur_s = s;
ll cur_n = N;
ll new_len = N;
FOR(i,N) {
index[i] = i;
}
FOR(x,30) {
bool prev = false;
vl next_s;
vl next_index;
ll next_n = 0;
ll cur_index = 0;
FOR(i,cur_n) {
if (cur_s[i] == x) {
if (prev == false) prev = true;
else {
prev = false;
next_s.push_back(x+1);
next_n++;
next_index.push_back(cur_index);
cur_index++;
}
} else {
if (prev == true) {
changes[index[i-1]].push_back(x);
new_len++;
prev = false;
next_s.push_back(x+1);
next_n++;
next_index.push_back(cur_index);
cur_index++;
}
next_s.push_back(cur_s[i]);
next_index.push_back(cur_index);
cur_index++;
next_n++;
}
}
if (prev == true) {
changes[index[cur_n-1]].push_back(x);
new_len++;
prev = false;
next_s.push_back(x+1);
next_n++;
next_index.push_back(cur_index);
cur_index++;
}
cur_s = next_s;
index = next_index;
cur_n = next_n;
//PRINTV(cur_s);
//PRINTV(index);
//PRINTVP(changes);
}
vl new_s;
ll target = N + K - new_len;
assert(target >= 0);
FOR(i,N) {
new_s.push_back(s[i]);
for (auto x:changes[i]) {
if (target == 0)
new_s.push_back(x);
else if (target >= pow(2,x)-1) {
FOR(_,pow(2,x)) {
new_s.push_back(0);
}
target -= pow(2,x)-1;
} else {
vl part = partsplit(x,target+1);
for (auto v: part) {
new_s.push_back(v);
}
target = 0;
}
}
}
PRINTV(new_s);
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |