Cod sursa(job #3131494)

Utilizator bogdanvladmihaiBogdan Vlad-Mihai bogdanvladmihai Data 20 mai 2023 13:45:17
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.21 kb
#include <iostream>
#include <vector>
#include <assert.h>

struct BIT {
  const int L = 15;
  int N;
  std::vector<int> tree;
  BIT(int N_) : N(N_), tree(N_ + 1) {
    for (int i = 0; i < N; i++) {
      update(i, 1);
    }
  }
  void update(int pos, int delta) {
    for (int i = ++pos; i <= N; i += (i & (-i))) {
      tree[i] += delta;
    }
  }
  int query(int pos) {
    int answer = 0;
    for (int i = ++pos; i > 0; i -= (i & (-i))) {
      answer += tree[i];
    }
    return answer;
  }
  int find(int value) {
    int l = 0, r = N - 1, answer = -1;
    while (l <= r) {
      int m = (l + r) / 2;
      if (query(m) >= value) {
        answer = m;
        r = m - 1;
      } else {
        l = m + 1;
      }
    }
    return answer;
  }
};

int main() {
  assert(freopen("schi.in", "r", stdin));
  assert(freopen("schi.out", "w", stdout));

  int N;
  std::cin >> N;
  std::vector<int> V(N);
  for (int &x : V) {
    std::cin >> x;
  }
  BIT DS(N);
  std::vector<int> answer(N);
  for (int i = N - 1; i >= 0; i--) {
    int pos = DS.find(V[i]);
    answer[pos] = i + 1;
    DS.update(pos, -1);
  }
  for (int &x : answer) {
    std::cout << x << "\n";
  }
  return 0;
}