#include <bits/stdc++.h>
#define maxn 1000005
using namespace std;
int n,k;
int a[maxn];
vector<int>sol;
int s[maxn];
void precalc()
{
s[0]=0;
for(int i=1;i<=n;i++)s[i]=s[i-1]+(1<<a[i]);
}
void solve(int l,int r,int x)
{
if(l>r)
{
sol.push_back(x);
return;
}
if(l==r)
{
int s=1<<x;
sol.push_back(a[l]);
s-=1<<a[l];
int br=0;
while(s>0)
{
if(s%2)sol.push_back(br);
br++;
s/=2;
}
return;
}
int left=l;
int right=r;
int br=1<<(x-1);
int t=l;
while(left<=right)
{
int mid=(left+right)/2;
if(s[mid]-s[l-1]>br)right=mid-1;
else {
t=mid;
left=mid+1;
}
}
solve(l,t,x-1);
solve(t+1,r,x-1);
}
int najv2(int x)
{
int l=0;
int r=30;
int sss=0;
while(l<=r)
{
int mid=(l+r)/2;
int br=(1<<mid)-1;
if(br>x)r=mid-1;
else{
sss=mid;
l=mid+1;
}
}
return sss;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin>>n>>k;
for(int i=1;i<=n;i++)cin>>a[i];
precalc();
solve(1,n,30);
int sz=sol.size();
int d=n+k-sz;
/*for(int i=0;i<sz;i++)
{
if(d==0)cout<<sol[i]<<" ";
else{
int mmm=najv2(d);
int minn=min(mmm,sol[i]);
for(int i=1;i<=(1<<minn);i++)cout<<sol[i]-minn<<" ";
d-=1<<minn;
d++;
}
}*/
for(auto x:sz)
{
if(d==0)cout<<x<<" ";
else{
int mmm=najv2(d);
int minn=min(mmm,x);
for(int i=1;i<=(1<<minn);i++)cout<<x-minn<<" ";
d-=1<<minn;
d++;
}
}
return 0;
}
Compilation message
zalmoxis.cpp: In function 'int main()':
zalmoxis.cpp:100:15: error: 'begin' was not declared in this scope
for(auto x:sz)
^~
zalmoxis.cpp:100:15: note: suggested alternatives:
In file included from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:95:0,
from zalmoxis.cpp:1:
/usr/include/c++/7/valarray:1211:5: note: 'std::begin'
begin(const valarray<_Tp>& __va)
^~~~~
/usr/include/c++/7/valarray:1211:5: note: 'std::begin'
zalmoxis.cpp:100:15: error: 'end' was not declared in this scope
for(auto x:sz)
^~
zalmoxis.cpp:100:15: note: suggested alternatives:
In file included from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:95:0,
from zalmoxis.cpp:1:
/usr/include/c++/7/valarray:1231:5: note: 'std::end'
end(const valarray<_Tp>& __va)
^~~
/usr/include/c++/7/valarray:1231:5: note: 'std::end'
