Cod sursa(job #37053)

Utilizator vlad_popaVlad Popa vlad_popa Data 24 martie 2007 15:40:27
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.07 kb
#include <cstdio>

#define FIN "schi.in"
#define FOUT "schi.out"
#define NMAX 30001

int v[NMAX], c[NMAX], N, temp[NMAX], rez[NMAX];

void read ()
{
  scanf ("%d", &N);

  for (int i = 1; i <= N; ++ i)
    scanf ("%d", &v[i]),
    temp[i] = i;
}

int LSB (int x)
{
  return x ^ (x - 1) & x;
}

int query (int x)
{
  int rez = 0;

  for (; x > 0; x -= LSB (x))
    rez += c[x];

  return rez;
}

void update (int x)
{
  for (; x <= N; x += LSB (x))
    c[x] += 1;
}

int binary_search (int val)
{
  int i, step;

  for (step = 1; step <= N; step <<= 1);
  for (i = 0; step; step >>= 1)
    if (temp[i + step] - query (i + step - 1) <= val && i + step <= N)
      i += step;

  return i;
}

void solve ()
{
  int poz;
  
  for (int i = N; i >= 1; -- i)
   {
     poz = binary_search (v[i]);
     update (poz);
     rez[temp[poz]] = i;
   }

  for (int i = 1; i <= N; ++ i)
    printf ("%d\n", rez[i]);
}

int
 main ()
{
  freopen (FIN, "rt", stdin);
  freopen (FOUT, "wt",stdout);
  
  read ();
  solve ();
  return 0;
}