Cod sursa(job #2920211)

Utilizator Alex_HossuHossu Alexandru Alex_Hossu Data 22 august 2022 20:18:52
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.99 kb
#include <stdio.h>

#define MAX_N 30001

int v[MAX_N];
int res[MAX_N];
int aib[MAX_N];

inline long long int query(int res) {
  long long int ans = 0;
  while (res) {
    ans += aib[res];
    res -= res & (-res);
  }
  return ans;
}

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

int main () {
  FILE *fin, *fout;
  int n, i;
  int st, dr, mij;

  fin = fopen("schi.in", "r");

  fscanf(fin, "%d", &n);
  for (i = 1; i <= n; i++) {
    fscanf(fin, "%d", &v[i]);
    update (i, 1, n);
  }

  fclose(fin);

  for (i = n; i > 0; i--) {
    st = 0, dr = n + 1;
    while (dr - st > 1) {
      mij = (st + dr) / 2;
      if (query(mij) < v[i])
        st = mij;
      else
        dr = mij;
    }
    res[++st] = i;
    update(st, -1, n);
  }

  fout = fopen("schi.out", "w");
  for (i = 1; i <= n; i++)
    fprintf(fout, "%d\n", res[i]);
  fclose(fout);

  return 0;
}