Pagini recente » Cod sursa (job #2216191) | Cod sursa (job #1289479) | Cod sursa (job #1280524) | Cod sursa (job #2917607) | Cod sursa (job #65424)
Cod sursa(job #65424)
#include<stdio.h>
struct nod
{ int disp;
nod *st;
nod *dr;
};
int n,max,i,c[30001],fin[30001],lloc;
nod *arb;
int distr(nod *pp,int mmax);
int ins(int loc,nod *p);
int main()
{
FILE *f,*g;
f=fopen("schi.in","r");
g=fopen("schi.out","w");
fscanf(f,"%d",&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,"%d",&c[i]);
for(i=n;i>=1;i--)
{ lloc=1;
ins(c[i],arb);
}
for(i=0;i<n;i++)
fprintf(g,"%d\n",fin[i]);
fcloseall();
return 0;
}
int distr(nod *pp,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;
}
int ins(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;
}