Pagini recente » Clasament Summer Challenge 2007 | Cod sursa (job #429883) | Cod sursa (job #335368) | Cod sursa (job #706424) | Cod sursa (job #3288772)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("farfurii.in");
ofstream fout("farfurii.out");
const int N=1e5+5;
struct aib
{
int n,v[N];
void init(int n)
{
for(int i=1;i<=n;++i)
{
v[i]=(i&-i);
}
}
void update(int p,int val)
{
for(int i=p;i<=n;i+=(i&-i))
{
v[i]+=val;
}
}
int query(int p)
{
int t=0;
if(!p) return 0;
for(int i=p;i;i-=(i&-i))
{
t+=v[i];
}
return t;
}
int bin(int val)
{
int st=1,dr=n,sol=0,mid;
while(st<=dr)
{
mid=(st+dr)>>1;
if(query(mid-1)>val)
{
dr=mid-1;
}
else
{
sol=mid;
st=mid+1;
}
}
return sol;
}
};
int n,i,j,r,sol[N];
long long k,f[N];
aib a;
void print()
{
for(i=1;i<=n;++i)
{
fout<<sol[i]<<' ';
}
}
int main()
{
ios_base::sync_with_stdio(false);
fin.tie(NULL);
fout.tie(NULL);
fin>>n>>k;
a.n=n;
a.init(n);
for(i=1;i<=n;++i)
{
f[i]=(1ll*i*(i-1)/2);
}
for(i=1;i<=n;++i)
{
if(f[n-i]>=k)
{
r=i;
sol[i]=i;
a.update(i,-1);
}
else
{
break;
}
}
for(i=r+1;i<=n;++i)
{
int lim=k-f[n-i];
int x=a.bin(lim);
k-=a.query(x-1);
a.update(x,-1);
sol[i]=x;
}
print();
return 0;
}