Last active
October 29, 2021 02:53
-
-
Save kumagi/062947d368ea461024b59244a0c0d226 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment