Advertisement
Guest User

Untitled

a guest
Mar 25th, 2019
60
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.24 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4.  
  5. using int64 = long long;
  6.  
  7. int64 n, m;
  8. std::vector<std::pair<int64, int64>> deer, elves;
  9.  
  10. bool check(int64 k)
  11. {
  12.     int64 j = 1;
  13.  
  14.     for (int64 i = 1; i <= m; ++i)
  15.     {
  16.         if (j > k)
  17.             continue;
  18.  
  19.         if (elves[j].first < deer[i].first && deer[i].first < elves[n - k + j].first)
  20.             ++j;
  21.     }
  22.  
  23.     return j > k;
  24. }
  25.  
  26. int main()
  27. {
  28.     std::cin >> m >> n;
  29.  
  30.     deer.assign(m + 1, { -1, -1 });
  31.     elves.assign(n + 1, { -1, -1 });
  32.  
  33.     for (int64 i = 1; i <= m; ++i)
  34.     {
  35.         std::cin >> deer[i].first;
  36.         deer[i].second = i;
  37.     }
  38.    
  39.     std::sort(deer.begin(), deer.end());
  40.  
  41.     for (int64 i = 1; i <= n; ++i)
  42.     {
  43.         std::cin >> elves[i].first;
  44.         elves[i].second = i;
  45.     }
  46.  
  47.     std::sort(elves.begin(), elves.end());
  48.  
  49.     int64 l = 0;
  50.     int64 r = std::min(m, n / 2) + 1;
  51.     int64 mid;
  52.  
  53.     while (r - l > 1)
  54.     {
  55.         mid = (l + r) / 2;
  56.         if (check(mid))
  57.             l = mid;
  58.         else
  59.             r = mid;
  60.     }
  61.  
  62.     std::cout << l << '\n';
  63.     int64 j = 1;
  64.  
  65.     for (int64 i = 1; i <= m; ++i)
  66.     {
  67.         if (j > l)
  68.             continue;
  69.  
  70.         if (elves[j].first < deer[i].first && deer[i].first < elves[n - l + j].first)
  71.         {
  72.             std::cout << deer[i].second << ' ' << elves[j].second << ' ' << elves[n - l + j].second << '\n';
  73.             ++j;
  74.         }
  75.     }
  76.     return 0;
  77. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement