Cod sursa(job #47180)

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

#define Nmax 30000
#define Mmax 60000

int n,poz[Nmax],nrpoz[Mmax],vst[Mmax],vdr[Mmax],i,k,lib;

void create(int a, int st, int dr)
{
   nrpoz[a]=dr-st+1;
   if (st==dr)
     {
        vst[a]=vdr[a]=-1;
        return;
     }
   int m=(st+dr)/2;
   vst[a]=lib++;
   create(vst[a],st,m);
   vdr[a]=lib++;
   create(vdr[a],m+1,dr);
}

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

   lib=1;
   create(0,0,n-1);
   for (i=n-1;i>=0;i--) dec(0,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;
}