Cod sursa(job #47192)

Utilizator marius135Dumitran Adrian Marius marius135 Data 3 aprilie 2007 13:53:17
Problema Schi Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.98 kb
#include<stdio.h>
#define max 64*1024

long v[max];
long st[max];
long dr[max];
long valdr[max],next=1;
long hst[max];
long hdr[max];
long r[max];
long t[max];

long adauga(long a,long b,long c,long d)
{
	if(a==1) {v[1] = a;return 1;}
	long w;
	if(v[b] == 0) {v[b] = a; return d;}
	if(valdr[b] >= c) 
		{
		if(dr[b]==0) dr[b]=++next;
		valdr[b]++;
		w = adauga(a,dr[b],c,d+1);
		if(w-d>hdr[b]) hdr[b] = w-d;
		return w;
		}
	if(st[b]==0) st[b]=++next;
	w = adauga(a,st[b],c-valdr[b]-1,d+1);
	if(w-d>hst[b]) hst[b] = w-d;
	return w;
	
}

void drs(long a)
{
	if(v[a]==0) return;
	drs(dr[a]);
	printf("%ld\n",v[a]);
	drs(st[a]);
}
long gaseste(long a,long b,long c,long d)
{
	if(b==c) return b;
	if(r[d*2]>=a) return gaseste(a,b,(b+c)/2,d*2);
	return gaseste(a-r[d*2],(b+c)/2+1,c,d*2+1);
	
}
void elimina(long a,long b,long c,long d)
{
	r[d]--;
	if(b==c) return;
	if(a<=(b+c)/2) elimina(a,b,(b+c)/2,d*2);
	else elimina(a,(b+c)/2+1,c,d*2+1);
}
void creaza(long a,long b,long c)
{
	r[a] = c-b+1;
	if(b==c) return;
	creaza(a*2,b,(b+c)/2);
	creaza(a*2+1,(b+c)/2+1,c);
}
int main()
{
	long i,n,x,a,b,c,rad=1,w;
	freopen("schi.in","r",stdin);
	freopen("schi.out","w",stdout);
	
	scanf("%ld",&n);
	for(i=1;i<=n;i++)
		scanf("%ld",&v[i]);
	
	creaza(1,1,n);
	for(i=n;i>=1;i--)
		{
		w = gaseste(v[i],1,n,1);
		t[w]=i;
		elimina(w,1,n,1);
		}
	for(i=1;i<=n;i++) printf("%ld\n",t[i]);
		
	
	/*for(i=1;i<=n;i++)
		{
		scanf("%ld",&x);
		adauga(i,rad,x-1,1);
		if(hdr[rad]>hst[rad]+3)
			{
			a = dr[rad];
			b = hst[a];
			valdr[rad] = valdr[rad]-valdr[a]-1;
			hst[a] = hst[rad ]+1;
			hdr[rad ] = b;
			c = st[a];
			st[a] = rad ;
			dr[rad ] = c;
			rad = a;
			}
		if(hst[rad ]>hdr[rad ]+3)
			{
			a = st[rad];
			b = hdr[a];
			valdr[a] = valdr[rad]+1;
			hdr[a] = hdr[rad ]+1;
			hst[rad ] = b;
			c = dr[a];
			dr[a] = rad ;
			st[rad ] = c;
			rad = a;
			
			}
		}
	i++;
	
	drs(rad);
		*/
	
	
	
	
	return 0;
}