Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <algorithm>
- #include <iostream>
- #include <utility>
- #include <vector>
- struct Entity {
- int64_t value;
- int64_t pos;
- };
- struct Comparator {
- bool operator()(Entity const &a, int64_t val) { return a.value < val; }
- bool operator()(int64_t val, Entity const &b) { return val < b.value; }
- bool operator()(Entity const &a, Entity const &b) {
- return a.value < b.value;
- }
- };
- Entity deers[100000];
- Entity elves[100000];
- int64_t Dcount;
- int64_t Ecount;
- bool checkCount(int64_t ExpDcount, bool isOut = false) {
- if (isOut) {
- std::cout << ExpDcount << "\n";
- }
- int64_t deersCount = 0;
- for (int64_t i = 0; i < ExpDcount; ++i) {
- for (int64_t j = 0; j < Dcount; ++j) {
- if (elves[i].value < deers[j].value
- && elves[Ecount + i - ExpDcount].value > deers[j].value) {
- if (isOut)
- std::cout << deers[j].pos << " " << elves[i].pos << " "
- << elves[Ecount + i - ExpDcount].pos << "\n";
- ++i;
- ++deersCount;
- }
- }
- }
- return deersCount >= ExpDcount;
- }
- int main() {
- std::cin >> Dcount >> Ecount;
- for (int64_t i = 0; i < Dcount; ++i) {
- std::cin >> deers[i].value;
- deers[i].pos = i + 1;
- }
- for (int64_t i = 0; i < Ecount; ++i) {
- std::cin >> elves[i].value;
- elves[i].pos = i + 1;
- }
- std::sort(elves, elves + Ecount, Comparator());
- std::sort(deers, deers + Dcount, Comparator());
- int64_t lhs = 0;
- int64_t rhs = std::min(Ecount / 2, Dcount) + 1;
- int64_t mid = 0;
- int64_t ans = 0;
- while (rhs - lhs > 1) {
- mid = (lhs + rhs) / 2;
- if (checkCount(mid)) {
- lhs = mid;
- ans = mid;
- } else {
- rhs = mid;
- }
- }
- checkCount(ans, true);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement