Cod sursa(job #1425463)

Utilizator isa_mirica_mihaiMirica Matei isa_mirica_mihai Data 27 aprilie 2015 15:42:06
Problema Schi Scor 100
Compilator cpp Status done
Runda pregatire-lot-aib Marime 0.97 kb
#include <cstdio>
int aib[30005], v[30005], f[30005];
int n;
void update(int poz, int val){
  for(poz; poz <= n; poz += poz & -poz)
    aib[poz] += val;
}
int query(int poz){
  int s = 0;
  for(poz; poz > 0; poz -= poz & -poz)
    s += aib[poz];
  return s;
}

int bs(int st, int dr, int val){
  int med, x, last;
  last = 2000000000;
  while (st <= dr){
    med = (st + dr) >> 1;
    x = query(med);
    if(x == val && med < last)
      last = med;
    else
        if(x < val)
            st = med + 1;
        else
            dr = med - 1;
  }
  return last;
}

int main()
{
    freopen("schi.in", "r", stdin);
    freopen("schi.out", "w", stdout);
    scanf("%d", &n);
    int i, x;
    for(i = 1; i <= n; i ++){
      scanf("%d", &v[i]);
      aib[i] = i & -i;
    }
    for(i = n; i > 0; i --){
      x = bs(1, n, v[i]);
      f[x] = i;
      update(x, -1);
    }
    for(i = 1; i <= n; i ++)
      printf("%d\n", f[i]);
    return 0;
}