#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,k,cnt;
set<pair<int,int>> rez;
vector<int> pozs[31];
int a[2000005],inita[2000005];
int nxt[2000005][2],prec[2000005][2];
void baga_dupa(int p, int x, int c)
{
int pnxt = nxt[p][c];
nxt[p][c] = x;
nxt[x][c] = pnxt;
prec[x][c] = p;
prec[pnxt][c] = x;
}
void scoate(int p, int c)
{
nxt[prec[p][c]][c] = nxt[p][c];
prec[nxt[p][c]][c] = prec[p][c];
}
vector<int> aux;
void calc(int x)
{
if(k==0 || x==0)
{
aux.push_back(x);
return;
}
k--;
calc(x-1);
calc(x-1);
}
signed main()
{
ios_base::sync_with_stdio(0);cin.tie(0);
cin>>n>>k;
int initn=n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
inita[i]=a[i];
prec[i][0]=prec[i][1]=i-1;
nxt[i][0]=nxt[i][1]=i+1;
pozs[a[i]].push_back(i);
}
nxt[n][0]=nxt[n][1]=0;
for(int i=0;i<30;i++)
{
sort(pozs[i].begin(),pozs[i].end());
for(int j=(int)pozs[i].size()-1;j>=0;j--)
{
if(j>0 && nxt[pozs[i][j-1]][0] == pozs[i][j])
{
//cout<<i<<" zzz\n";
pozs[i+1].push_back(pozs[i][j]);
a[pozs[i][j]]++;
scoate(pozs[i][j-1],0);
j--;
}
else
{
pozs[i+1].push_back(pozs[i][j]);
k--;
n++;
a[n]=inita[n]=i;
baga_dupa(pozs[i][j],n,1);
a[pozs[i][j]]++;
}
}
/*cout<<i<<" ";
int cur=1;
while(cur!=0)
{
cout<<a[cur]<<" ";
cur = nxt[cur][0];
}
cout<<"\n";*/
}
assert(n<=2000000);
int primu=-1;
for(int i=1;i<=n;i++)
if(prec[i][0]==0)
primu=i;
assert(primu!=-1);
for(int i=primu;i<=n;i++)
{
if(cur<=initn) aux.push_back(inita[cur]);
else calc(inita[cur]);
cur = nxt[cur][1];
}
for(auto x:aux)
cout<<x<<" ";
return 0;
}
/**
5 1
29 27 25 25 28
1 5
29
*/
Compilation message
zalmoxis.cpp: In function 'int main()':
zalmoxis.cpp:91:12: error: 'cur' was not declared in this scope
91 | if(cur<=initn) aux.push_back(inita[cur]);
| ^~~
zalmoxis.cpp:93:9: error: 'cur' was not declared in this scope
93 | cur = nxt[cur][1];
| ^~~
