Cod sursa(job #47176)

Utilizator georgianaGane Andreea georgiana Data 3 aprilie 2007 13:31:41
Problema Schi Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.25 kb
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define Nmax 30000

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

void create(arb a, int st, int 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)
{
   int st=0, dr=n-1, m;
   while (st!=dr)
     {
        a->nrpoz--;
        m=(st+dr)/2;
        if (a->vst->nrpoz>=k) { a=a->vst; dr=m; }
        else {
                k-=a->vst->nrpoz;
                a=a->vdr;
                st=m+1;
             }
     }
   a->nrpoz=0;
   poz[st]+=i;
}

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

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

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