Cod sursa(job #2117884)

Utilizator vladcainamisirVlad Cainamisir vladcainamisir Data 29 ianuarie 2018 19:18:20
Problema Schi Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.49 kb
#include <stdio.h>

const int MAX_N = 30000;

int n;
int AIB[1 + MAX_N];

int sum(int k) {
  int suma = 0;
  while (k > 0) {
    suma += AIB[k];
    k &= k - 1;
  }
  return suma;
}

void add(int index, int value) {
  while (index <= n) {
    AIB[index] += value;
    index += index & -index;
  }
}

/*
int kth(int k) {
  int st = 0, dr = n, loc = 0;
  while (st <= dr) {
    int mid = (st + dr) / 2;
    int value = sum(mid);
    if (value == k) {
      loc = mid;
      dr = mid - 1;
    } else if (value < k)
      st = mid + 1;
    else
      dr = mid - 1;
  }
  return loc;
}//*/

/*
int kth(int k) {
  int loc = 0;
  for (int step = 1 << 14; step > 0; step >>= 1)
    if (loc + step <= n && sum(loc + step) < k)
      loc += step;
  loc++;
  return loc;
}//*/

int kth(int k) {
  int loc = 0;
  int suma = 0;
  for (int step = 1 << 14; step > 0; step >>= 1)
    if (loc + step <= n && suma + AIB[loc + step] < k) {
      loc += step;
      suma += AIB[loc + step];
    }
  loc++;
  return loc;
}



int main() {
  freopen("schi.in", "r", stdin);
  freopen("schi.out", "w", stdout);
  scanf("%d", &n);
  int Loc[1 + n];
  int Clasament[1 + n];
  for (int i = 1; i <= n; i++)
    scanf("%d", &Loc[i]);
  for (int i = 1; i <= n; i++)
    add(i, 1);
  for (int i = n; i >= 1; i--) {
    Loc[i] = kth(Loc[i]);
    Clasament[Loc[i]] = i;
    add(Loc[i], -1);
  }
  for (int i = 1; i <= n; i++)
    printf("%d\n", Clasament[i]);
  return 0;
}