Cod sursa(job #47022)

Utilizator georgianaGane Andreea georgiana Data 3 aprilie 2007 12:10:55
Problema Schi Scor 65
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.21 kb
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define Nmax 30000

struct nod
        {
           int st, dr, nrpoz;
           struct nod* vst;
           struct nod* vdr;
        };
typedef struct nod* arb;
int n,poz[Nmax],h[Nmax],i,k;
arb a;

void create(arb a, int st, int dr)
{
   a->st=st; a->dr=dr;
   a->nrpoz=dr-st+1;
   if (st==dr)
     {
        a->vst=a->vdr=NULL;
        return;
     }
   int m=(st+dr)/2;
   a->vst=(arb)malloc(sizeof(struct nod));
   create(a->vst,st,m);
   a->vdr=(arb)malloc(sizeof(struct nod));
   create(a->vdr,m+1,dr);
}

void dec(arb a, int k)
{
   while (a->st!=a->dr)
     {
        a->nrpoz--;
        if (a->vst->nrpoz>=k) a=a->vst;
        else {
                k-=a->vst->nrpoz;
                a=a->vdr;
             }
     }
   a->nrpoz=0;
   h[a->st]=i;
}

int main()
{
   freopen("schi.in","r",stdin);
   scanf("%d\n",&n);
   for (i=0;i<n;i++) scanf("%d",&poz[i]);

   a=(arb)malloc(sizeof(struct nod));
   create(a,0,n-1);
   memset(h,0,sizeof(h));
   for (i=n-1;i>=0;i--) dec(a,poz[i]);

   freopen("schi.out","w",stdout);
   for (i=0;i<n;i++)
      printf("%d\n",h[i]+1);
   fclose(stdout);
   return 0;
}