Cod sursa(job #211725)

Utilizator recviemAlexandru Pana recviem Data 3 octombrie 2008 15:07:45
Problema Schi Scor 75
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.33 kb
#include <stdio.h>

#define nmax 60000
using namespace std;

void citire();
int build_tree(int nod,int x, int y);
int query(int nod, int x, int y);
//void solve();

int n;
int a[nmax],tree[nmax],sol[nmax],p,val;

int main()
{
    citire();
    build_tree(1, 1, n);
    for (int i=n-1;i>=0;i--)
    {
        val = a[i];
        p = i;
        sol[query(1,1,n)-1] = i+1;
    }
    freopen("schi.out","w",stdout);
    for (int i=0;i<n;i++)
        printf("%d\n",sol[i]);
    return 0;
}

int query(int nod, int x, int y)
{
    int left  = (nod << 1), right = (nod << 1)+1, mid = (x+y)>>1;

    if (x == y)
    {
        tree[nod] = 0;
        return x;
    }

    if (val <= tree[left])
    {
        int rez = query(left,x,mid);
        tree[nod]-- ;
        return rez;
    }

    val -= tree[left];
    int rez = query(right,mid+1,y);
    tree[nod] -- ;
    return rez;

}

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

int build_tree(int nod, int x, int y)
{
    int left  = (nod << 1),
        right = (nod << 1)+1,
        mid   = (x+y)>>1;
    if (x > y)
        return 0;
    if (x == y)
        return tree[nod] = 1;

    return tree[nod] = build_tree(left,x,mid) + build_tree(right,mid+1,y);
}