Cod sursa(job #2232814)

Utilizator mihailescu_eduardMihailescu Eduard-Florin mihailescu_eduard Data 21 august 2018 10:49:11
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.06 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()
{
    int i;
    scanf("%d",&n);
    for(i = 1; i<= n; ++i)
    {
        scanf("%d",&v[i]);
        Add(i,1);
    }

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

int main()
{
    Read();
    for(int i = 1; i<= n; ++i)
    {
        printf("%d\n",sol[i]);
    }
}