Cod sursa(job #2113410)

Utilizator stefan_creastaStefan Creasta stefan_creasta Data 24 ianuarie 2018 15:45:37
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.02 kb
#include <cstdio>
#define nrzero(x) (x ^ (x - 1)) & x
using namespace std;
const int NMAX = 30005;
int v[NMAX];
int sol[NMAX];
int aib[2 * NMAX];
void update(int poz, int n, int val) {
  while(poz <= n) {
    aib[poz] += val;
    poz += nrzero(poz);
  }
}
int query(int poz) {
  int sol = 0;
  while(poz > 0) {
    sol += aib[poz];
    poz -= nrzero(poz);
  }
  return sol;
}
int aa(int x, int n) {
  int st = 1, dr = n, sol = 0;
  while(st <= dr) {
    int mij = (st + dr) / 2;
    int sum = query(mij);
    if(sum == x) {
      sol = mij;
      dr = mij - 1;
    }
    else if(sum < x) {
      st = mij + 1;
    }
    else {
      dr = mij - 1;
    }
  }
  return sol;
}

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