Cod sursa(job #904741)

Utilizator lianaliana tucar liana Data 4 martie 2013 20:13:19
Problema Farfurii Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.03 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("%ld %ld",&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;
       // a=a+sum;
        update(1,n,1);
        ne--;
    }
    return 0;
}