people_array.cpp

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

class BIT {
public:
  explicit BIT(size_t n) : tree(n + 2) {}

  int sum(size_t index) const {
    int sum = 0;
    index += 1;
    while (0 < index) {
      sum += tree[index];
      index -= index & -index;
    }
    return sum;
  }

  void update(size_t index, int val) {
    index += 1;
    while (index <= tree.size() - 1) {
       tree[index] += val;
       index += index & -index;
    }
  }

private:
  vector<int> tree;
};

struct Person {
  int height = 0;
  int taller = 0;
  friend ostream& operator<<(ostream& o, const Person& p) {
    o << "{" << p.height << ", " << p.taller << "}";
    return o;
  }
};

vector<Person> reconstruct_order(vector<Person>& people) {
  BIT bit(people.size());
  for (size_t i = 0; i < people.size(); ++i) {
    bit.update(i, 1);
  }
  sort(people.begin(), people.end(),
       [](const auto &a, const auto &b) { return a.height < b.height; });
  
  vector<Person> ans(people.size());
  for (const auto& p : people) {
    int l = -1, r = people.size();
    while (1 < r - l) {
      int mid = (l + r) / 2;
      if (bit.sum(mid) - 1 < p.taller)
        l = mid;
      else
        r = mid;
    }
    ++l;
    ans[l] = p;
    bit.update(l, -1);
  }
  return ans;
}

int main() {
  vector<Person> people{Person{1, 1}, Person{2, 2}, Person{3, 0}, Person{4, 1},
                        Person{5, 0}};
  auto ans = reconstruct_order(people);
  for (const auto& p : ans) {
    cout << p << "\n";
  }
  return 0;
}