Cod sursa(job #1991755)

Utilizator victoreVictor Popa victore Data 18 iunie 2017 12:37:30
Problema Farfurii Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.25 kb
#include<cstdio>

const int nmax=1e5+5;

int arb[4*nmax+66];

int n;
long long k;

inline void update(int node,int st,int dr,int pos,int val)
{
    if(st==dr)
    {
        arb[node]+=val;
        return;
    }
    int med=(st+dr)>>1;
    if(pos>med)
        update(2*node+1,med+1,dr,pos,val);
    else
        update(2*node,st,med,pos,val);
    arb[node]=arb[2*node]+arb[2*node+1];
}

inline int query(int node,int st,int dr,long long pos)
{
    if(st==dr)
        return st;
    int med=(st+dr)>>1;
    if(arb[2*node]>=pos)
        return query(2*node,st,med,pos);
    pos-=arb[2*node];
    return query(2*node+1,med+1,dr,pos);
}

int main()
{
    freopen("farfurii.in","r",stdin);
    freopen("farfurii.out","w",stdout);
    int i,pos;
    scanf("%d%i64d",&n,&k);
    long long temp;
    for(i=1;i<=n;++i)
        update(1,1,n,i,1);
    for(i=n;i;i--)
    {
        if(k <= 1LL*(i-1)*(i-2)/2)
        {
            pos=query(1,1,n,1);
            update(1,1,n,pos,-1);
            printf("%d ",pos);
        }
        else
        {
            temp=k-1LL*(i-1)*(i-2)/2;
            k=k-temp;
            pos=query(1,1,n,temp+1);
            update(1,1,n,pos,-1);
            printf("%d ",pos);
        }
    }
}