Cod sursa(job #827057)

Utilizator maritimCristian Lambru maritim Data 1 decembrie 2012 16:12:36
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.26 kb
#include<stdio.h>

FILE *f = fopen("schi.in","r");
FILE *g = fopen("schi.out","w");

#define MaxN 30100
#define mij ((li+ls)>>1)
#define fs (poz<<1)
#define fd ((poz<<1)+1)

int N;
int A[MaxN],AINT[4*MaxN],SolV[MaxN];

void citire(void)
{
    fscanf(f,"%d",&N);
    for(int i=1;i<=N;i++)
        fscanf(f,"%d",&A[i]);
}

inline void build(int li,int ls,int poz)
{
    if(li == ls)
    {
        AINT[poz] = 1;
        return ;
    }

    build(li,mij,fs);
    build(mij+1,ls,fd);

    AINT[poz] = AINT[fs]+AINT[fd];
}

inline void update(int li,int ls,int poz,int pozVal)
{
    if(li == ls)
    {
        AINT[poz] = 0;
        return ;
    }

    if(li <= pozVal && pozVal <= mij)
        update(li,mij,fs,pozVal);
    else
        update(mij+1,ls,fd,pozVal);

    AINT[poz] = AINT[fs]+AINT[fd];
}

inline int querry(int li,int ls,int poz,int pozS)
{
    if(li == ls)
        return li;

    if(AINT[fs] >= pozS)
        return querry(li,mij,fs,pozS);
    else
        return querry(mij+1,ls,fd,pozS-AINT[fs]);
}

void Rezolvare(void)
{
    int a;
    build(1,N,1);

    for(int i=N;i;i--)
    {
        a = querry(1,N,1,A[i]);
        SolV[a] = i;
        update(1,N,1,a);
    }
}

int main()
{
    citire();
    Rezolvare();

    for(int i=1;i<=N;i++)
        fprintf(g,"%d\n",SolV[i]);
}