Cod sursa(job #59016)

Utilizator crawlerPuni Andrei Paul crawler Data 7 mai 2007 21:59:15
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.85 kb
#include <cstdio>

using namespace std;

#define Nmax 30100

int v[Nmax], a[Nmax], p[Nmax], n;

void update(int x,int val)
 {
  for(;x<=n; x+= x^(x-1)&x)
   a[x] += val;
 }

int query(int x)
 {
  int r=0;
  for(;x; x-= x^(x-1)&x)
   r += a[x];
  return r;
 }

int search(int val)
 {
  int st,dr,mij;
  st = 1;
  dr = n;
  while(st < dr)
   {
    mij = (st+dr)/2;
    if(query(mij) < val)
     st = mij+1;
      else
     dr = mij;
   }
  return st;
 }

int main()
 {
  freopen("schi.in","r",stdin);
  freopen("schi.out","w",stdout);

  int i, tmp;

  scanf("%d",&n);

  for(i=n;i>0;--i)
   scanf("%d", v+i);

  for(i=1;i<=n;++i)
   update(i,1);

  for(i=1;i<=n;++i)
   {
    tmp = search(v[i]);
    update(tmp,-1);
    p[tmp] = n-i+1;
   }

  for(i=1;i<=n;++i)
   printf("%d\n",p[i]);

  return 0;
 }