#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;
vl count(num+1);
ll amount = 1;
count[num] = 1;
while(amount < t) {
FORS(i,1,num+1) {
if (count[i] > 0) {
count[i]--;
count[i-1]+=2;
break;
}
}
//PRINTV(count);
//scout << amount << NL;
amount++;
}
FOR(i,num+1) {
FOR(_,count[i]) {
res.push_back(i);
}
}
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);
}
//PRINTVV(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 |
179 ms |
67904 KB |
not a zalsequence |
| 2 |
Incorrect |
165 ms |
69212 KB |
not a zalsequence |
| 3 |
Incorrect |
169 ms |
68728 KB |
not a zalsequence |
| 4 |
Incorrect |
163 ms |
68104 KB |
not a zalsequence |
| 5 |
Incorrect |
173 ms |
68800 KB |
not a zalsequence |
| 6 |
Incorrect |
159 ms |
68396 KB |
not a zalsequence |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
172 ms |
68880 KB |
not a zalsequence |
| 2 |
Incorrect |
158 ms |
76972 KB |
not a zalsequence |
| 3 |
Incorrect |
180 ms |
72136 KB |
not a zalsequence |
| 4 |
Incorrect |
164 ms |
68904 KB |
not a zalsequence |
| 5 |
Incorrect |
164 ms |
68284 KB |
not a zalsequence |
| 6 |
Incorrect |
160 ms |
67500 KB |
not a zalsequence |
| 7 |
Incorrect |
167 ms |
69292 KB |
not a zalsequence |
| 8 |
Incorrect |
165 ms |
68680 KB |
not a zalsequence |
| 9 |
Incorrect |
165 ms |
66032 KB |
not a zalsequence |
| 10 |
Incorrect |
104 ms |
37368 KB |
not a zalsequence |
| 11 |
Incorrect |
141 ms |
44404 KB |
not a zalsequence |
| 12 |
Incorrect |
63 ms |
14672 KB |
not a zalsequence |
| 13 |
Incorrect |
71 ms |
13460 KB |
not a zalsequence |
| 14 |
Correct |
63 ms |
13396 KB |
Output is correct |
