Cod sursa(job #35789)

Utilizator mariusdrgdragus marius mariusdrg Data 22 martie 2007 15:36:42
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.11 kb
#include<stdio.h>

const int maxn = 32001;

int aib[maxn];
int a[maxn], a1[maxn];
int i;
int n;
int j;
int poz;


inline int lsb(int a)
{
        return a ^ (a & ( a - 1));
}

void update(int poz,int sum)
{
        while(poz <= n)
        {
                aib[poz] += sum;
                poz += lsb(poz);
        }
}

int querry(int poz)
{

        int sum = 0;
        while(poz)
        {
                sum += aib[poz];
                poz -= lsb(poz);
        }
        return sum;
}

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]);
        }
        for(j = n;j > 0; --j)
        {
                poz = a[j];
                int pozin = -1;
                while(poz != pozin)
                {
                        pozin = poz;
                        poz = a[j] + querry(poz);
                }
                a1[poz] = j;
                update(poz, 1);
        }
        for(i = 1;i <= n; ++i)
        {
                printf("%d\n",a1[i]);
        }
        
        return 0;
}