Cod sursa(job #65395)

Utilizator anna_bozianuBozianu Ana anna_bozianu Data 9 iunie 2007 11:49:28
Problema Schi Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.33 kb
#include<stdio.h>
struct nod
{       long int poz;
	long int niv;
	long int max;
	long int disp;
	nod *st;
	nod *dr;
};
long int q,n,nivm,i,c[30001],fin[30001],pow=1;
nod *arb;
long int distr(nod *pp);
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,"%ld",&n);
	arb=new nod;arb->max=1;arb->niv=1;
	while(arb->max<=n){arb->max*=2;arb->niv++;}
	if(arb->max==2*n){ arb->max=n;arb->niv--;}
	arb->poz=1;arb->disp=n;
	distr(arb);
	for(i=1;i<=n;i++)
	 fscanf(f,"%ld",&c[i]);
	q=2*arb->max;
	for(i=n;i>=1;i--)
	 ins(c[i],arb);
	q=2*arb->max;
	for(i=1;i<=n;i++)
	fprintf(g,"%ld\n",fin[i]);
	fcloseall();
	return 0;
}
long int distr(nod *pp)
{
	nod *p1,*p2;
	int dis;
	p1=new nod;p2=new nod;
	p1->poz=2*pp->poz+1;p2->poz=2*pp->poz;
	p1->niv=pp->niv-1;p2->niv=pp->niv-1;
	p1->max=pp->max/2;p2->max=pp->max/2;
	dis=pp->disp;
	if(dis<=p1->max){p1->disp=dis;p2->disp=0;}
	else {p1->disp=p1->max;p2->disp=dis-p1->max;}
	pp->st=p1;
	pp->dr=p2;
	if(p1->max>1){distr(pp->st);distr(pp->dr);}
	else{ pp->st->st=0;pp->st->dr=0;pp->dr->st=0;pp->dr->dr=0;}
	return 0;
}
long int ins(long int loc,nod *p)
{
	p->disp--;
	if(p->niv==1) {fin[q-p->poz]=i;return 0;}
	if(loc>p->st->disp) { ins(loc-p->st->disp,p->dr);return 0;}
	ins(loc,p->st);
	return 0;
}