#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fbo find_by_order
#define ook order_of_key
typedef long long ll;
typedef pair<int,int> pi;
typedef vector<ll> vi;
typedef long double ld;
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> pbds;
typedef set<ll>::iterator sit;
typedef map<ll,ll>::iterator mit;
typedef pair<int,pair<int,int> > tri;
int n, k;
int a[1000050];
set<pi> s;
//set<int> pos;
multiset<int> s2;
vector<int> add[1000050];
int addnum = 0;
int need;
int cnt[35];
int nxt[1000050];
int tem = 0;
void split(int k1){
assert(k1>=0);
for(int i = 0; i < 35; i++) cnt[i] = 0;
cnt[k1] = 1;
//cout<<"SPLIT "<<k1<<endl;
int j = 0;
while(need){
//if(need>-10 && need < 10000)cout<<"NEED : "<<need<<endl;
if(k1==0) break;
if(cnt[k1]>0){
cnt[k1]--;
cnt[k1-1] +=2;
need --;
}
else k1--;
}
for(int i = 0; i <= 30; i++){
for(int j = 0; j < cnt[i]; j++){
cout << i << ' ';
//tem++;
}
}
}
int main()
{
//ios_base::sync_with_stdio(0); cin.tie(0);
//freopen("8z.in","r",stdin);
cin >> n >> k;
for(int i = 0; i < n; i++){
scanf("%d",&a[i]);
s.insert(mp(a[i],i));
//assert(a[i] == 0);
//pos.insert(i);
if(i!=n-1) nxt[i] = i+1;
else nxt[i] = -1;
}
while(1){
auto it = s.begin();
pi p = *it;
//cout<<p.fi<<endl;
if(s.size()==1){
if(p.fi==30) break;
else{
for(int i = p.fi; i <= 29; i++){
add[p.se].pb(i);
//assert(i>0);
addnum++;
}
s.erase(it);
s.insert(mp(30,p.se));
}
}
else{
auto it2 = ++it;
pi next = *it2;
it--;
if(p.fi == next.fi && nxt[p.se] == next.se){
s.erase(it2);
// pos.erase(next.se);
nxt[p.se] = nxt[next.se];
s.erase(it);
s.insert(mp(p.fi+1, p.se));
}
else{
add[p.se].pb(p.fi);
//cout<<p.fi<<endl;
//assert(p.fi>0);
addnum ++;
s.erase(it);
s.insert(mp(p.fi+1, p.se));
}
}
}
need = k - addnum;
for(int i = 0; i < n; i++){
for(int j = add[i].size()-1; j >= 0; j--){
assert(add[i][j] >= 0);
if(need > 0) split(add[i][j]);
else{
printf("%d ",add[i][j]);
//tem ++;
}
}
printf("%d ",a[i]);
//tem++;
//cout<<"I: "<< i << endl;
}
//cout<<tem;
return 0;
}
Compilation message
zalmoxis.cpp: In function 'void split(int)':
zalmoxis.cpp:42:9: warning: unused variable 'j' [-Wunused-variable]
int j = 0;
^
zalmoxis.cpp: In function 'int main()':
zalmoxis.cpp:70:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&a[i]);
~~~~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
872 ms |
80888 KB |
Output is correct |
| 2 |
Correct |
877 ms |
80908 KB |
Output is correct |
| 3 |
Correct |
893 ms |
80908 KB |
Output is correct |
| 4 |
Correct |
891 ms |
81000 KB |
Output is correct |
| 5 |
Correct |
858 ms |
81000 KB |
Output is correct |
| 6 |
Correct |
865 ms |
81000 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
894 ms |
81000 KB |
Output is correct |
| 2 |
Correct |
871 ms |
81000 KB |
Output is correct |
| 3 |
Correct |
924 ms |
81000 KB |
Output is correct |
| 4 |
Correct |
919 ms |
81000 KB |
Output is correct |
| 5 |
Correct |
864 ms |
81000 KB |
Output is correct |
| 6 |
Correct |
904 ms |
81000 KB |
Output is correct |
| 7 |
Correct |
900 ms |
81000 KB |
Output is correct |
| 8 |
Correct |
875 ms |
81000 KB |
Output is correct |
| 9 |
Correct |
789 ms |
81000 KB |
Output is correct |
| 10 |
Correct |
391 ms |
81000 KB |
Output is correct |
| 11 |
Correct |
606 ms |
81000 KB |
Output is correct |
| 12 |
Correct |
115 ms |
81000 KB |
Output is correct |
| 13 |
Correct |
119 ms |
81000 KB |
Output is correct |
| 14 |
Correct |
110 ms |
81000 KB |
Output is correct |
