Cod sursa(job #2232926)

Utilizator mihailescu_eduardMihailescu Eduard-Florin mihailescu_eduard Data 21 august 2018 17:33:27
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.04 kb
#include <cstdio>

#define lsb(x) (x & (-x))

FILE *fin = freopen("schi.in","r",stdin); FILE *fout = freopen("schi.out","w",stdout);

const int NMAX = 30000 + 5;

/* -------- Data -----------*/
int n, v[NMAX], aib[NMAX], sol[NMAX];
/* -------- Data -----------*/

void Add(int position, int value)
{
    for(int i = position; i<= n; i+=lsb(i))
        aib[i]+=value;
}

int Query(int position)
{
    int res = 0;
    for(int i = position; i>0 ; i-=lsb(i))
        res+=aib[i];
    return res;
}

void Read()
{
    scanf("%d",&n);
    for(int i =1 ; i<= n; ++i){
        scanf("%d",&v[i]);
        Add(i,1);
    }
}

void Rezolva()
{
    int pas = 1, k = 0,aux;
    for(;pas<=n;pas<<=1);

    for(int i = n; i>= 1; i--)
    {
        aux = pas; k = 0;
        for(;aux;aux>>=1)
            if(k + aux <= n && Query(k+aux) < v[i])
                k+=aux;
        sol[k+1]=i;
        Add(k+1,-1);
    }
    for(int i = 1; i<= n; ++i)
        printf("%d\n",sol[i]);
}

int main()
{
    Read();
    Rezolva();

}