Cod sursa(job #252864)

Utilizator eugen.nodeaEugen Nodea eugen.nodea Data 4 februarie 2009 23:41:22
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.91 kb
# include <stdio.h>
# define dim 30001

int N, M;
int Arb[4*dim+66],V[dim],Sol[dim];
int val, poz,p;
void Upd(int nod, int st, int dr)
{
   int mij;
   if (st==dr) Arb[nod] = val;
	else {
		mij = (st+dr)/2;
		if (poz<=mij) Upd(2*nod,st,mij);
			 else Upd(2*nod+1,mij+1,dr);
		Arb[nod]=Arb[2*nod]+Arb[2*nod+1];
	    }
}
int Query(int nod, int st, int dr, int val)
{
     if ( st==dr) return st;
     int mij = (st+dr)/2;
     if (val<= Arb[2*nod] ) return Query(2*nod,st,mij,val);
		       else return Query(2*nod+1,mij+1,dr,val-Arb[2*nod]);
}

int main()
{
    int i;
    freopen("schi.in", "r", stdin);
    freopen("schi.out", "w", stdout);
    scanf("%d", &N);
    for (i=1;i<=N;i++){
	scanf("%d", &V[i]);
	poz=i; val=1; Upd(1,1,N);
    }
    for (i=N;i>0;i--){
	p=Query(1,1,N,V[i]);
	poz=p; val=0; Sol[p]=i;
	Upd(1,1,N);
    }
    for (i=1;i<=N;i++)
	printf("%d\n",Sol[i]);
    return 0;
}