| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 74005 | 2018-08-29T15:30:05 Z | vex | Zalmoxis (BOI18_zalmoxis) | C++14 | 0 ms | 0 KB |
#include <bits/stdc++.h>
#define maxn 1000005
using namespace std;
int n,k;
int a[maxn];
vector<int>sol;
int s[maxn];
bool bio[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);
bio[sol.size()-1]=false;
return;
}
if(l==r)
{
int is=1<<x;
sol.push_back(a[l]);
bio[sol.size()-1]=true;
is-=1<<a[l];
int br=0;
while(is>0)
{
if(is%2)
{
sol.push_back(br);
bio[sol.size()-1]=false;
br++;
is/=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 || bio[i])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++;
}
}
return 0;
}