Advertisement
Alex-Flexer

Untitled

Jul 25th, 2024
7
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.90 KB | None | 0 0
  1. #include <iostream>
  2. #include <string>
  3. #include <queue>
  4. #include <map>
  5. #include <vector>
  6. #include <set>
  7. #include <cmath>
  8. #include <iomanip>
  9. #include <algorithm>
  10. #include <fstream>
  11. #include <unordered_map>
  12. #include <stack>
  13.  
  14. typedef long long ll;
  15. using namespace std;
  16.  
  17. int n, t;
  18. vector<pair<int, int>> v;
  19. map<pair<int, int>, int> m;
  20.  
  21. bool cmp(pair<int, int>& a, pair<int, int>& b)
  22. {
  23. return (a.second == b.second ? a.first >= b.first : a.second < b.second);
  24. }
  25.  
  26. // res pos
  27. pair<int, int> f(int pos, bool& was_timeout)
  28. {
  29. pair<int, int> res_without_timeout {0, -1};
  30. pair<int, int> res_with_timeout {0, -1};
  31.  
  32. bool was_timeout_copy = was_timeout;
  33.  
  34. for (int i = pos + 1; i < n; ++i)
  35. {
  36. if (v[pos].second <= v[i].first)
  37. {
  38. pair<int, int> tmp = f(i, was_timeout);
  39. if (was_timeout)
  40. {
  41. res_without_timeout = tmp;
  42. ++res_without_timeout.first;
  43. break;
  44. }
  45. }
  46. }
  47.  
  48. if (was_timeout_copy)
  49. return res_without_timeout;
  50.  
  51. for (int i = pos + 1; i < n; ++i)
  52. {
  53. if (v[i].first - v[pos].second >= t)
  54. {
  55. was_timeout = true;
  56. res_with_timeout = f(i, was_timeout);
  57. ++res_with_timeout.first;
  58. res_with_timeout.second = pos;
  59. break;
  60. }
  61. }
  62.  
  63. return max(res_without_timeout, res_with_timeout);
  64. }
  65.  
  66. int main()
  67. {
  68. cin >> n >> t;
  69. v.resize(n);
  70. for (int i = 0; i < n; ++i)
  71. {
  72. cin >> v[i].first >> v[i].second;
  73. m[v[i]] = i + 1;
  74. }
  75.  
  76. sort(v.begin(), v.end(), cmp);
  77.  
  78. bool was_timeout = false;
  79. int timeout_pos = f(0, was_timeout).second;
  80. if (timeout_pos == -1)
  81. {
  82. cout << -1;
  83. return 0;
  84. }
  85.  
  86. vector<pair<int, int>> res;
  87.  
  88. for (int i = 0; i < n; i++)
  89. {
  90. if (res.empty() || v[i].first - res.back().second >= (res.size() == timeout_pos ? t : 0))
  91. res.push_back(v[i]);
  92. }
  93.  
  94. if (res.size() == 0)
  95. {
  96. cout << -1;
  97. return 0;
  98. }
  99.  
  100. cout << res.size() << endl;
  101. for (int i = 0; i < res.size(); ++i)
  102. cout << m[res[i]] << ' ';
  103. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement