Cod sursa(job #681202)

Utilizator crushackPopescu Silviu crushack Data 16 februarie 2012 19:25:46
Problema Schi Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.99 kb
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define NMax 100010

const char IN[]="schi.in",OUT[]="schi.out";

struct nod{
	short x,key,n;
	nod *l,*r;
} *NIL=new nod,*T=NIL;

int N;
short v[NMax] , R[NMax];

void init(){
	NIL->x=NIL->key=NIL->n=0;
	NIL->l=NIL->r=NULL;
}

nod* rotr(nod *T)
{
	nod *t=T->l;
	T->l=t->r;t->r=T;
	
	T->n=T->l->n+T->r->n;
	t->n=t->l->n+t->r->n;
	return t;
}

nod* rotl(nod *T)
{
	nod *t=T->r;
	T->r=t->l;t->l=T;
	
	T->n=T->l->n+T->r->n+1;
	t->n=t->l->n+t->r->n+1;
	return t;
}

nod* insert(nod *T,short x,short key)
{
	if (T==NIL)
	{
		nod *aux=new nod;
		aux->l=aux->r=NIL;
		aux->x=x;aux->key=key;aux->n=1;
		T= aux;
	}
	else if ( x<T->x )
	{
		T->l=insert(T->l,x,key);
		if (T->l->key > T->key ) T= rotr(T);
	}
	else
	{
		T->r=insert(T->r,x,key);
		if (T->r->key > T->key) T= rotl(T);
	}
	T->n=T->l->n+T->r->n+1;
	return T;
}

nod *erase(nod *T,short x)
{
	if (T==NIL) return NIL;
	if ( x<T->x)
		T->l=erase(T->l,x);
	else if ( x>T->x)
		T->r=erase(T->r,x);
	else
	{
		if (T->l==NIL && T->r==NIL) 
		{
			delete T;
			return NIL;
		}
		
		if ( T->l->key > T->r->key ) 
			T=rotr(T),T->r=erase(T->r,x);
		else T=rotl(T),T->l=erase(T->l,x);
	}
	T->n=T->l->n+T->r->n+1;
	if (T->l!=NIL) T->l->n=T->l->l->n+T->l->r->n+1;
	if (T->r!=NIL) T->r->n=T->r->l->n+T->r->r->n+1;
	return T;
}

nod* query(nod*T,int val)
{
	if ( T->l == NIL && T->r==NIL ) return T;
	if (T->l->n==val-1) return T;
	if ( T->l->n < val )
		return query(T->r,val-T->l->n-1);
	return query(T->l,val);
}

int main()
{
	int i,x;
	srand(time(NULL)*rand());
	freopen(IN,"r",stdin);
	scanf("%d",&N);
	for (i=1;i<=N;++i) scanf("%d",&x),v[i]=x;
	fclose(stdin);
	
	init();
	for (i=1;i<=N;++i) 
		T=insert(T,i,rand());
	
	for (i=N;i>0;--i)
	{
		nod *node=query(T,v[i]);
		R[node->x]=i;
		T=erase(T,node->x);
	}
	freopen(OUT,"w",stdout);
	for (i=1;i<=N;++i) x=R[i],printf("%d\n",x);
	fclose(stdout);
	
	return 0;
}