| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 644371 | Kripton | Zalmoxis (BOI18_zalmoxis) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
int steve[1000001],vf;
int steve1[1000001],vf1;
int v[1000001],v1[1000001];
vector <int> addie[1000001];
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n,k,i,j;
cin>>n>>k;
v[0]=-1;
int rez=0;
for(i=1;i<=n;i++)
{
cin>>v[i];
rez+=(1<<v[i]);
v1[i]=v[i];
while(v[i]==v[steve[vf]])
{
v[i]++;
vf--;
}
steve[++vf]=i;
}
for(j=1;j<=40&&v[steve[vf]]!=30;j++)
{
int min1=40;
for(i=1;i<=vf;i++)
min1=min(min1,v[steve[i]]);
vf1=0;
for(i=1;i<=vf;i++)
{
if(v[steve[i]]==min1)
{
k--;
v[steve[i]]++;
addie[steve[i]].push_back(min1);
rez+=(1<<min1);
}
while(v[steve[i]]==v[steve1[vf1]])
{
v[steve[i]]++;
vf1--;
}
steve1[++vf1]=steve[i];
}
vf=vf1;
for(i=1;i<=vf;i++)
steve[i]=steve1[vf1];
}
assert(rez==(1<<30));
for(i=1;i<=n;i++)
{
cout<<v1[i]<<" ";
rez+=(1<<v1[i]);
for(auto it:addie[i])
{
if(k>=((1<<it)-1))
{
k-=((1<<it)-1);
for(j=1;j<=(1<<it);j++)
cout<<"0 ";
rez+=(1<<it);
continue;
}
else if(k)
{
int a=(int)log2(k)+1;
int newit=it-a;
//daca fac (1<<a) newit-uri, k-=((1<<a)-1)
k=((1<<a)-1)-k;
for(j=1;j<=(1<<a)-2*k;j++)
cout<<newit<<" ";
rez+=(1<<newit)*((1<<a)-2*k);
for(j=1;j<=k;j++)
cout<<newit+1<<" ";
rez+=(1<<(newit+1))*k;
k=0;
}
else
{
cout<<it<<" ";
rez+=(1<<it);
}
}
}
return 0;
}