#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 |
| 1 |
Incorrect |
178 ms |
69224 KB |
not a zalsequence |
| 2 |
Incorrect |
170 ms |
69096 KB |
not a zalsequence |
| 3 |
Incorrect |
155 ms |
69296 KB |
not a zalsequence |
| 4 |
Incorrect |
170 ms |
68620 KB |
not a zalsequence |
| 5 |
Incorrect |
160 ms |
69436 KB |
not a zalsequence |
| 6 |
Incorrect |
162 ms |
68924 KB |
not a zalsequence |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
164 ms |
67912 KB |
not a zalsequence |
| 2 |
Incorrect |
162 ms |
74040 KB |
not a zalsequence |
| 3 |
Incorrect |
169 ms |
73996 KB |
not a zalsequence |
| 4 |
Incorrect |
195 ms |
67628 KB |
not a zalsequence |
| 5 |
Incorrect |
164 ms |
67708 KB |
not a zalsequence |
| 6 |
Incorrect |
169 ms |
67644 KB |
not a zalsequence |
| 7 |
Incorrect |
165 ms |
67984 KB |
not a zalsequence |
| 8 |
Incorrect |
199 ms |
68680 KB |
not a zalsequence |
| 9 |
Incorrect |
181 ms |
64744 KB |
not a zalsequence |
| 10 |
Incorrect |
105 ms |
35928 KB |
not a zalsequence |
| 11 |
Incorrect |
135 ms |
43668 KB |
not a zalsequence |
| 12 |
Incorrect |
64 ms |
14896 KB |
not a zalsequence |
| 13 |
Incorrect |
64 ms |
12880 KB |
not a zalsequence |
| 14 |
Incorrect |
61 ms |
12540 KB |
not a zalsequence |
