Cod sursa(job #3319761)

Utilizator RaresHRares Hanganu RaresH Data 3 noiembrie 2025 10:44:57
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.02 kb
#include <stdio.h>

const int MAX_N = 30'000;

struct Aib {
  int n;
  int aib[MAX_N + 1];

  void init(int _n) {
    n = _n;
  }

  void update(int pos, int delta) {
    for(; pos <= n; pos += pos & -pos) {
      aib[pos] += delta;
    }
  }

  int find_idx(int idx) {
    int ret = 0;
    int curr = 0;
    for(int i = 20; i >= 0; i--) {
      int new_ret = ret + (1 << i);
      if(new_ret <= n && new_ret - curr - aib[new_ret] - 1 < idx) {
        ret = new_ret;
        curr += aib[new_ret];
      }
    }
    return ret + 1;
  }
};

int a[MAX_N];
int ans[MAX_N];
Aib aib;

int main() {
  FILE* fin = fopen("schi.in", "r");
  FILE* fout = fopen("schi.out", "w");

  int n;
  fscanf(fin, "%d", &n);

  for(int i = 0; i < n; i++) {
    fscanf(fin, "%d", &a[i]);
    a[i]--;
  }

  aib.init(n);
  for(int i = n - 1; i >= 0; i--) {
    int idx = aib.find_idx(a[i]) - 1;
    ans[idx] = i;
    aib.update(idx + 1, 1);
  }

  for(int i = 0; i < n; i++) {
    fprintf(fout, "%d\n", ans[i] + 1);
  }

  fclose(fin);
  fclose(fout);

  return 0;
}