Cod sursa(job #214828)

Utilizator dragosmihaiDragos Oana dragosmihai Data 16 octombrie 2008 11:37:17
Problema Schi Scor 75
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.05 kb
#include <stdio.h>
#include <fstream>
using namespace std;

int a[30001],n,cls[30001],sir[30001];

int nr0(int x)
{
    int nr=0;
    while(!(x&1))
    {
        x>>=1;
        nr++;
    }
    return nr;
}

void aduna(int i,int x)
{
    while(i<=n)
    {
        a[i]+=x;
        i+=(1<<nr0(i));
    }
}

long suma(int i)
{
    long s=0;
    while(i>0)
    {
        s+=a[i];
        i-=(1<<nr0(i));
    }
    return s;
}

int poz(int x)
{
    int p;
    for(p=1;p<n;p<<=1);

    int z;
    for(z=n;p!=0;p>>=1)
        if(z-p>=1)
            if(x<=suma(z-p))
                z-=p;
    return z;
}

void citire()
{
    freopen("schi.in","r",stdin);
    freopen("schi.out","w",stdout);
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&sir[i]);
        aduna(i,1);
    }
    for(int i=n;i>0;i--)
    {
        int z=poz(sir[i]);
        cls[z]=i;
        aduna(z,-1);
    }
    for(int i=1;i<=n;i++)
        printf("%d\n",cls[i]);
}

int main()
{
    citire();
    return 0;
}