Advertisement
Guest User

Untitled

a guest
Dec 12th, 2019
85
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.77 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. //подключает всю STL C++
  3.  
  4. using namespace std;
  5.  
  6. #define do(_, n) for(int _ = 1; _ < n + 1; _++)
  7. //упрощает работу с индексами
  8.  
  9. #define _getchar_nolock getchar_unlocked
  10. //Без этого дефайна информатикс (GCC < 7.0.0) выдает ошибку
  11.  
  12. long long FastIntInput() {
  13. long long a = 0;//Вводимое число
  14. char c = ' ';
  15. bool f = false;//Булево на a < 0
  16. while (!isdigit(c)){//Считываем то, что между цифрами
  17. c = _getchar_nolock();/*Как getchar(), но не блокирует
  18. во время работы потоки помимо cin, за счет чего работает быстрее*/
  19. if (c == '-')
  20. f = true;
  21. }
  22. while (isdigit(c)) {
  23. a = a * 10 + (c - '0');
  24. c = _getchar_nolock();
  25. }
  26. if (f)
  27. return -a;
  28. return a;
  29. }
  30.  
  31. void debug(set<int> &b)
  32. {
  33. for(auto i : b)
  34. cout << i << ' ';
  35. cout << '\n';
  36. }
  37. //простите, что не написал эти две функции через шаблоны, просто спать хотелось
  38. void debug(vector<int> &b)
  39. {
  40. for(auto i : b)
  41. cout << i << ' ';
  42. cout << '\n';
  43. }
  44.  
  45. int main(){
  46. int m = FastIntInput(), n = FastIntInput();
  47. vector<int> a = {-1}, b = {-1};
  48. do(_, m)
  49. a.push_back(FastIntInput());
  50. do(_, n)
  51. b.push_back(FastIntInput());
  52. multimap<int, int> b_izn, a_izn;
  53. do(_, m)
  54. a_izn.insert({a[_], _});
  55. do(_, n)
  56. b_izn.insert({b[_], _});
  57. sort(a.begin(), a.end());
  58. sort(b.begin(), b.end());
  59. int l = 0, r = min(m, n / 2) + 1;
  60. while(r - l > 1)
  61. {
  62. int mid = (r + l) / 2;
  63. bool povozka = true; // показывает, можно ли составить повозку
  64. set<int> a_copy = {-1};
  65. do(i, m){
  66. a_copy.insert(a[i]);
  67. }
  68. do(i, mid){
  69. int one = b[i];
  70. int two = b[n - mid + i];
  71. bool ok = false;
  72. int deer = *lower_bound(a.begin(), a.end(), one);
  73. if(deer > one && deer < two){
  74. ok = true;
  75. a_copy.erase(deer);
  76. break;
  77. }
  78. if(!ok)
  79. povozka = false;
  80. }
  81. //debug(a_copy);
  82. if(povozka)
  83. l = mid;
  84. else
  85. r = mid;
  86. }
  87. int mid = (r + l) / 2;
  88. cout << mid << '\n';
  89. multiset<int> a_copy = {-1};
  90. do(i, m){
  91. a_copy.insert(a[i]);
  92. }
  93. do(i, mid){
  94. int one = b[i];
  95. int two = b[n - mid + i];
  96. int deer = *(a_copy.lower_bound(one));
  97. a_copy.erase(a_copy.find(deer));
  98. int first = (*b_izn.find(one)).second;
  99. int second = (*b_izn.find(two)).second;
  100. int dear_izn = (*a_izn.find(deer)).second;
  101. cout << dear_izn << ' ' << first << ' ' << second << '\n';
  102. a_izn.erase(a_izn.find(deer));
  103. b_izn.erase(b_izn.find(two));
  104. b_izn.erase(b_izn.find(one));
  105. }
  106. return 0;
  107. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement