Cod sursa(job #1994870)

Utilizator DruffbaumPopescu Vlad Druffbaum Data 26 iunie 2017 14:05:26
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.07 kb
#include <cstdio>

const int INF = 2e9;
const int MAXN = 3e4;

int v[MAXN + 1], ans[MAXN + 1],
    aib[MAXN + 1];

inline void update(int x, int val, int n) {
  while (x <= n) {
    aib[x] += val;
    x += x & -x;
  }
}

inline int sum(int x) {
  int s = 0;
  while (x) {
    s += aib[x];
    x -= x & -x;
  }
  return s;
}

inline int cautBin(int val, int n) {
  int l, r, m, x, min;
  l = 1;
  r = n;
  min = INF;
  while (l <= r) {
    m = (l + r) >> 1;
    x = sum(m);
    if ((x == val) && (m < min)) {
      min = m;
    } else if (x < val) {
      l = m + 1;
    } else {
      r = m - 1;
    }
  }
  return min;
}

int main() {
  int n, x;
  FILE *f = fopen("schi.in", "r");
  fscanf(f, "%d", &n);
  for (int i = 1; i <= n; ++i) {
    fscanf(f, "%d", &v[i]);
    update(i, 1, n);
  }
  fclose(f);
  for (int i = n; i > 0; --i) {
    x = cautBin(v[i], n);
    ans[x] = i;
    update(x, -1, n);
  }
  f = fopen("schi.out", "w");
  for (int i = 1; i <= n; ++i) {
    fprintf(f, "%d\n", ans[i]);
  }
  fclose(f);
  return 0;
}