Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <string>
- #include <queue>
- #include <map>
- #include <vector>
- #include <set>
- #include <cmath>
- #include <iomanip>
- #include <algorithm>
- #include <fstream>
- #include <unordered_map>
- #include <stack>
- typedef long long ll;
- using namespace std;
- int n, t;
- vector<pair<int, int>> v;
- map<pair<int, int>, int> m;
- bool cmp(pair<int, int>& a, pair<int, int>& b)
- {
- return (a.second == b.second ? a.first >= b.first : a.second < b.second);
- }
- // res pos
- pair<int, int> f(int pos, bool& was_timeout)
- {
- pair<int, int> res_without_timeout {0, -1};
- pair<int, int> res_with_timeout {0, -1};
- bool was_timeout_copy = was_timeout;
- for (int i = pos + 1; i < n; ++i)
- {
- if (v[pos].second <= v[i].first)
- {
- pair<int, int> tmp = f(i, was_timeout);
- if (was_timeout)
- {
- res_without_timeout = tmp;
- ++res_without_timeout.first;
- break;
- }
- }
- }
- if (was_timeout_copy)
- return res_without_timeout;
- for (int i = pos + 1; i < n; ++i)
- {
- if (v[i].first - v[pos].second >= t)
- {
- was_timeout = true;
- res_with_timeout = f(i, was_timeout);
- ++res_with_timeout.first;
- res_with_timeout.second = pos;
- break;
- }
- }
- return max(res_without_timeout, res_with_timeout);
- }
- int main()
- {
- cin >> n >> t;
- v.resize(n);
- for (int i = 0; i < n; ++i)
- {
- cin >> v[i].first >> v[i].second;
- m[v[i]] = i + 1;
- }
- sort(v.begin(), v.end(), cmp);
- bool was_timeout = false;
- int timeout_pos = f(0, was_timeout).second;
- if (timeout_pos == -1)
- {
- cout << -1;
- return 0;
- }
- vector<pair<int, int>> res;
- for (int i = 0; i < n; i++)
- {
- if (res.empty() || v[i].first - res.back().second >= (res.size() == timeout_pos ? t : 0))
- res.push_back(v[i]);
- }
- if (res.size() == 0)
- {
- cout << -1;
- return 0;
- }
- cout << res.size() << endl;
- for (int i = 0; i < res.size(); ++i)
- cout << m[res[i]] << ' ';
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement