Cod sursa(job #912143)

Utilizator apopeid13Apopeid Alejandro apopeid13 Data 12 martie 2013 09:33:10
Problema Farfurii Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.77 kb
#include<stdio.h>
#define nmax 100005
#define pozmax 263000
long long n, k, poz, nrformmax, ne, a, sum;
long long s[pozmax];
void query(long st, long dr, long nod)
{
long mjc;
sum+=s[nod];
mjc=(st+dr)/2;
if (st<dr)
{
if (a<=mjc)
query(st,mjc,2*nod);
if (mjc+1<=a)
query(mjc+1,dr,2*nod+1);
}
}
void update(long st, long dr, long nod)
{
long mjc;
if (a<=st)
s[nod]++;
else
{
mjc=(st+dr)/2;
if (a<=mjc)
update(st,mjc,2*nod);
update(mjc+1,dr,2*nod+1);
}
}
int main()
{
freopen("farfurii.in","r",stdin);
freopen("farfurii.out","w",stdout);
scanf("%lld %lld",&n,&k);
ne=n;
for (poz=1;poz<=n;poz++)
{
nrformmax=(ne-1)*(ne-2)/2;
a=k+1-nrformmax;
if (a<=0)
a=1;
sum=0;
query(1,n,1);
printf("%ld ",a+sum); k-=a-1;
update(1,n,1);
ne--;
}
return 0;
}