Cod sursa(job #74674)

Utilizator andrei_infoMirestean Andrei andrei_info Data 26 iulie 2007 22:17:15
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.41 kb
#include <stdio.h>

#define MAX 30010


int sir[MAX], aib[MAX],N,rez[MAX];

void citire()
{
        freopen("schi.in", "r", stdin);
        scanf("%d", &N);
        for (int i=0; i<N; i++)
                scanf("%d\n", &sir[i]);
        fclose(stdin);
}

void update(int poz, int val)
{
        for ( ; poz<=N; poz += (poz ^ (poz-1)) & poz )
                aib[poz]+=val;
}

int query(int poz)
{
        int sum =0;
        for ( ; poz > 0; poz -= (poz ^ (poz-1)) & poz)
                sum +=aib[poz];
        return sum;
}

int bsearch( int val )
{
        int a=1, b=N,c,rez,p;
        for ( ; a<=b; )
        {
               c = (a+b) >> 1;
               rez = query(c);
               if (rez >= val)
               {
                        p=c;
                        b=c-1;
               }
               else
                        a=c+1;
        }
return p;
}

void solve()
{
        for (int i = 1; i<=N; i++)
                update(i,1);
        for (int i = N-1; i>=0; i--)
        {
                int r = bsearch(sir[i]);
                rez[r] = i+1;
                update(r,-1);
        }
}

void afisare()
{
        freopen("schi.out", "w", stdout);
        for (int i = 1; i<=N; i++)
                printf("%d\n", rez[i]);
        fclose(stdout);
}

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