Cod sursa(job #2681705)

Utilizator cristi_macoveiMacovei Cristian cristi_macovei Data 6 decembrie 2020 13:42:20
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.21 kb
#include <iostream>
#include <fstream>

const int NMAX = 3e4;

int n;

int a[1 + NMAX];

int ord[1 + NMAX];

int seg_tree[3 * NMAX];

void read() {
  std::ifstream in("schi.in");

  in >> n;

  for (int i = 1; i <= n; ++i) {
    in >> a[i];
  }

  in.close();
}

void build(int node, int left, int right) {
  if (left == right) {
    seg_tree[node] = 1;
    return;
  }

  int mid = (left + right) / 2;
  int left_child  = node * 2;
  int right_child = node * 2 + 1;

  build(left_child, left, mid);
  build(right_child, mid + 1, right);

  seg_tree[node] = seg_tree[left_child] + seg_tree[right_child];
}

int b_search(int node, int left, int right, int val) {
  --seg_tree[node];

  if (left == right) {
    return left;
  }

  int mid = (left + right) / 2;
  int left_child  = node * 2;
  int right_child = node * 2 + 1;

  if (val <= seg_tree[left_child])
    return b_search(left_child, left, mid, val);
  else
    return b_search(right_child, mid + 1, right, val - seg_tree[left_child]);
}

int main() {
  read();

  build(1, 1, n);

  for (int i = n; i >= 1; --i) {
    int ind = b_search(1, 1, n, a[i]);

    ord[ind] = i;
  }

  std::ofstream out("schi.out");
  for (int i = 1; i <= n; ++i)
    out << ord[i] << '\n';

  return 0;
}