Cod sursa(job #74662)

Utilizator anna_bozianuBozianu Ana anna_bozianu Data 26 iulie 2007 21:14:54
Problema Schi Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.35 kb
#include<stdio.h>
struct nod
{       unsigned long int disp;
	nod *st;
	nod *dr;
};
unsigned long int n,max,i,c[30001],fin[30001],lloc;
nod *arb;
unsigned long int distr(nod *pp,unsigned long int mmax);
unsigned long int ins(long int loc,nod *p);
int main()
{
	FILE *f,*g;
	f=fopen("schi.in","r");
	g=fopen("schi.out","w");
	fscanf(f,"%lu",&n);
	arb=new nod;arb->disp=n;arb->st=0;arb->dr=0;
	max=1;
	do
	max*=2;
	while(max<n);
	distr(arb,max);
	for(i=1;i<=n;i++)
	 fscanf(f,"%lu",&c[i]);
	for(i=n;i>=1;i--)
	 { lloc=1;
	   ins(c[i],arb);
	 }
	for(i=0;i<n;i++)
	fprintf(g,"%lu\n",fin[i]);
	fcloseall();
	return 0;
}
unsigned long int distr(nod *pp,unsigned long int mmax)
{
	nod *p1,*p2;
	if(mmax==1)
	{pp->st=0;
	pp->dr=0;
	return 0;}
	if(pp->disp<=mmax/2)
	{  p1=new nod;
	   p1->disp=pp->disp;
	   pp->st=p1;
	   pp->dr=0;
	   distr(pp->st,mmax/2);
	   return 0;
	}
	p1=new nod;p2=new nod;
	p1->disp=mmax/2;
	p2->disp=pp->disp-mmax/2;
	pp->st=p1;
	pp->dr=p2;
	distr(pp->st,mmax/2);
	distr(pp->dr,mmax/2);
	return 0;
}


unsigned long int ins(unsigned long int loc,nod *p)
{
	if(!p->st&&!p->dr)
	{ fin[lloc-max]=i;
	  p->disp--;
	  return 0;
	}

	if(loc>p->st->disp)
	{ lloc=2*lloc+1;
	  ins(loc-p->st->disp,p->dr);
	  p->disp--;
	  return 0;
	}
	lloc=2*lloc;
	ins(loc,p->st);
	p->disp--;
	return 0;
}