Cod sursa(job #1112239)

Utilizator octavdOctavian Dumitrascu octavd Data 19 februarie 2014 16:40:49
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.97 kb
#include <cstdio>
#define LSB(x) ((-x)&x)
using namespace std;

int aib[30005],a[30005],sol[30005],i,N,poz;


void Update(int V,int Pos)
{
    int i;
    for(i=Pos;i<=N;i=i+LSB(i))
            aib[i]=aib[i]+V;
}

int query(int Pos)
{
    int i,s=0;
    for(i=Pos; i>0; i-=LSB(i))
            s=s+aib[i];
    return s;
}

int verific_binar(int a)
{
    int pas,i;
    pas=1;
    while(pas<=N) pas=pas<<1;
    i=N;
    while (pas>0)
        {
            if (i-pas>0&&query(i-pas)>=a) i-=pas;
            pas=pas>>1;
        }
    return i;
}

int main()
{
    freopen("schi.in","r",stdin);
    freopen("schi.out","w",stdout);
    scanf("%d",&N);
    for( i = 1; i <= N; i++ )
    {
        scanf("%d",&a[i]);
        Update(1,i);
    }
    for (i=N;i>=1;i--)
        {
            poz=verific_binar(a[i]);
            sol[poz]=i;
            Update(-1,poz);
        }
    for (i=1;i<=N;i++)
        printf("%d\n",sol[i]);
    return 0;
}