Cod sursa(job #1223285)

Utilizator catalinrebegeaUNIBUC-Claudia Catarig catalinrebegea Data 25 august 2014 23:36:44
Problema Farfurii Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.25 kb
#include <cstdio>
#define Nmax 100005

using namespace std;

int aint[3*Nmax],a[Nmax],N;

inline void Update(int nod, int st, int dr, int x, int val)
{
    if(st==dr)
    {
        aint[nod]=1-val;
        return;
    }
    int mij=(st+dr)/2;
    if(x<=mij)
        Update(2*nod,st,mij,x,val);
    else
        Update(2*nod+1,mij+1,dr,x,val);
    aint[nod]=aint[2*nod]+aint[2*nod+1];
}

inline int Query(int nod, int st, int dr, long long k)
{
    if(st==dr)
        return st;
    int mij=(st+dr)/2;
    if(aint[2*nod]>=k)
        return Query(2*nod,st,mij,k);
    else
        return Query(2*nod+1,mij+1,dr,k-aint[2*nod]);
}

int main()
{
    long long K,aux;
    int i;
    freopen ("farfurii.in","r",stdin);
    freopen ("farfurii.out","w",stdout);
    scanf("%d%lld", &N,&K);
    for(i=1;i<=N;++i)
        Update(1,1,N,i,0);
    for(i=1;i<=N;++i)
    {
        aux=K-1LL*(N-i)*(N-i-1)/2;
        if(aux<=0)
        {
            a[i]=Query(1,1,N,1);
            Update(1,1,N,a[i],1);
        }
        else
        {
            K-=aux;
            a[i]=Query(1,1,N,aux+1);
            Update(1,1,N,a[i],1);
        }
    }
    for(i=1;i<=N;++i)
        printf("%d ", a[i]);
    printf("\n");
    return 0;
}