Advertisement
Jasuse

Untitled

Dec 11th, 2019
114
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.77 KB | None | 0 0
  1. #include <algorithm>
  2. #include <iostream>
  3. #include <utility>
  4. #include <vector>
  5.  
  6. struct Entity {
  7.   int64_t value;
  8.   int64_t pos;
  9. };
  10.  
  11. struct Comparator {
  12.   bool operator()(Entity const &a, int64_t val) { return a.value < val; }
  13.   bool operator()(int64_t val, Entity const &b) { return val < b.value; }
  14.   bool operator()(Entity const &a, Entity const &b) {
  15.     return a.value < b.value;
  16.   }
  17. };
  18.  
  19. Entity deers[100000];
  20. Entity elves[100000];
  21. int64_t Dcount;
  22. int64_t Ecount;
  23.  
  24. bool checkCount(int64_t ExpDcount, bool isOut = false) {
  25.   if (isOut) {
  26.     std::cout << ExpDcount << "\n";
  27.   }
  28.   int64_t deersCount = 0;
  29.   for (int64_t i = 0; i < ExpDcount; ++i) {
  30.       for (int64_t j = 0; j < Dcount; ++j) {
  31.           if (elves[i].value < deers[j].value
  32.               && elves[Ecount + i - ExpDcount].value > deers[j].value) {
  33.               if (isOut)
  34.                 std::cout << deers[j].pos << " " << elves[i].pos << " "
  35.                   << elves[Ecount + i - ExpDcount].pos << "\n";
  36.               ++i;
  37.               ++deersCount;
  38.           }
  39.       }
  40.   }
  41.   return deersCount >= ExpDcount;
  42. }
  43.  
  44. int main() {
  45.   std::cin >> Dcount >> Ecount;
  46.   for (int64_t i = 0; i < Dcount; ++i) {
  47.     std::cin >> deers[i].value;
  48.     deers[i].pos = i + 1;
  49.   }
  50.   for (int64_t i = 0; i < Ecount; ++i) {
  51.     std::cin >> elves[i].value;
  52.     elves[i].pos = i + 1;
  53.   }
  54.  
  55.   std::sort(elves, elves + Ecount, Comparator());
  56.   std::sort(deers, deers + Dcount, Comparator());
  57.  
  58.   int64_t lhs = 0;
  59.   int64_t rhs = std::min(Ecount / 2, Dcount) + 1;
  60.   int64_t mid = 0;
  61.   int64_t ans = 0;
  62.   while (rhs - lhs > 1) {
  63.     mid = (lhs + rhs) / 2;
  64.     if (checkCount(mid)) {
  65.       lhs = mid;
  66.       ans = mid;
  67.     } else {
  68.       rhs = mid;
  69.     }
  70.   }
  71.  
  72.   checkCount(ans, true);
  73.   return 0;
  74. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement