Pagini recente » Cod sursa (job #1249529) | Cod sursa (job #65397)
Cod sursa(job #65397)
#include<stdio.h>
struct nod
{ int poz;
int niv;
int max;
int disp;
nod *st;
nod *dr;
};
int q,n,nivm,i,c[30001],fin[30001],pow=1;
nod *arb;
int distr(nod *pp);
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->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,"%d",&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,"%d\n",fin[i]);
fcloseall();
return 0;
}
int distr(nod *pp)
{
if(pp->disp==0) return 0;
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;
}
int ins(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;
}