Pagini recente » Cod sursa (job #2924534) | Cod sursa (job #2925641) | Cod sursa (job #2430957) | Cod sursa (job #161992) | Cod sursa (job #681202)
Cod sursa(job #681202)
#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;
}