#include <bits/stdc++.h>
#define fr(i, n, m) for(int i = (n); i < (m); i ++)
#define pb push_back
#define st first
#define nd second
#define pq priority_queue
#define all(x) begin(x),end(x)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
ll const inf = 1e9;
ll const mod = 998244853;
ld const eps = 1e-9;
bool f(pii A, pii B){
if(A.st < B.st) return true;
else if(A.st > B.st) return false;
else A.nd > B.nd;
}
int k;
void expand(int num){
if(num == 0){
cout << 0 <<' ';
return;
}
if(k == 0){
cout << num <<' ';
return;
}
--k;
expand(num - 1);
expand(num - 1);
}
int main()
{
int n;
cin >> n >> k;
int a[n];
int b[n];
int MIN = 40;
int nxt[n];
fr(i, 0, n){
cin >> a[i];
b[i] = a[i];
MIN = min(a[i], MIN);
nxt[i] = i + 1;
}
nxt[n - 1] = n;
vector<pii> v;
int sz = n;
fr(mi, MIN, 30){
int p = 0;
int CNT = 0;
fr(i, 0, sz){
if(nxt[p] == n){
if(a[p] == mi){
v.pb({p, mi});
a[p] ++;
}
}
else if(a[p] == mi){
if(a[nxt[p]] == mi){
a[p] = mi + 1;
nxt[p] = nxt[nxt[p]];
CNT ++;
}
else{
v.pb({p, mi});
a[p] = mi + 1;
}
}
p = nxt[p];
}
sz -= CNT;
p = 0;
}
sort(v.begin(), v.end(), f);
int j = 0;
k -= v.size();
fr(i, 0, n){
while(j < v.size() && v[j].st == i){
int c = 0;
int ai = v[j].nd;
if((1 << ai) <= k){
k -= (1 << ai);
fr(o, 0, (1 << ai)) cout << 0 <<' ';
}
else{
expand(v[j].nd);
}
j ++;
}
cout << b[i] <<' ';
}
cout <<endl;
return 0;
}
Compilation message
zalmoxis.cpp: In function 'bool f(pii, pii)':
zalmoxis.cpp:21:20: warning: statement has no effect [-Wunused-value]
else A.nd > B.nd;
^
zalmoxis.cpp: In function 'int main()':
zalmoxis.cpp:89:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(j < v.size() && v[j].st == i){
~~^~~~~~~~~~
zalmoxis.cpp:90:29: warning: unused variable 'c' [-Wunused-variable]
int c = 0;
^
zalmoxis.cpp: In function 'bool f(pii, pii)':
zalmoxis.cpp:22:1: warning: control reaches end of non-void function [-Wreturn-type]
}
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
404 ms |
16260 KB |
Output is correct |
| 2 |
Correct |
435 ms |
16232 KB |
Output is correct |
| 3 |
Correct |
403 ms |
16220 KB |
Output is correct |
| 4 |
Incorrect |
424 ms |
16280 KB |
Expected EOF |
| 5 |
Incorrect |
430 ms |
16872 KB |
Expected EOF |
| 6 |
Incorrect |
413 ms |
16368 KB |
Expected EOF |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
410 ms |
16292 KB |
not a zalsequence |
| 2 |
Correct |
405 ms |
16248 KB |
Output is correct |
| 3 |
Incorrect |
409 ms |
16252 KB |
Unexpected end of file - int32 expected |
| 4 |
Incorrect |
405 ms |
16252 KB |
not a zalsequence |
| 5 |
Correct |
414 ms |
16244 KB |
Output is correct |
| 6 |
Correct |
404 ms |
16396 KB |
Output is correct |
| 7 |
Incorrect |
409 ms |
16256 KB |
Unexpected end of file - int32 expected |
| 8 |
Incorrect |
413 ms |
16416 KB |
not a zalsequence |
| 9 |
Incorrect |
374 ms |
14692 KB |
Unexpected end of file - int32 expected |
| 10 |
Incorrect |
221 ms |
7712 KB |
not a zalsequence |
| 11 |
Incorrect |
281 ms |
10676 KB |
Unexpected end of file - int32 expected |
| 12 |
Runtime error |
2 ms |
376 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 13 |
Runtime error |
2 ms |
376 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 14 |
Incorrect |
98 ms |
2296 KB |
Unexpected end of file - int32 expected |
