#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+1);
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 |
154 ms |
67744 KB |
not a zalsequence |
| 2 |
Incorrect |
163 ms |
68840 KB |
not a zalsequence |
| 3 |
Incorrect |
163 ms |
67688 KB |
not a zalsequence |
| 4 |
Incorrect |
164 ms |
67984 KB |
not a zalsequence |
| 5 |
Incorrect |
156 ms |
69368 KB |
not a zalsequence |
| 6 |
Incorrect |
155 ms |
69068 KB |
not a zalsequence |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
165 ms |
69032 KB |
not a zalsequence |
| 2 |
Incorrect |
165 ms |
74672 KB |
not a zalsequence |
| 3 |
Incorrect |
167 ms |
75052 KB |
not a zalsequence |
| 4 |
Incorrect |
165 ms |
67988 KB |
not a zalsequence |
| 5 |
Incorrect |
171 ms |
67772 KB |
not a zalsequence |
| 6 |
Incorrect |
164 ms |
68124 KB |
not a zalsequence |
| 7 |
Incorrect |
163 ms |
67960 KB |
not a zalsequence |
| 8 |
Incorrect |
165 ms |
68940 KB |
not a zalsequence |
| 9 |
Incorrect |
162 ms |
62788 KB |
not a zalsequence |
| 10 |
Incorrect |
112 ms |
35588 KB |
not a zalsequence |
| 11 |
Incorrect |
133 ms |
43800 KB |
not a zalsequence |
| 12 |
Incorrect |
75 ms |
13136 KB |
not a zalsequence |
| 13 |
Incorrect |
66 ms |
14136 KB |
not a zalsequence |
| 14 |
Correct |
63 ms |
13908 KB |
Output is correct |
