This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "bits/stdc++.h"
using namespace std;
#ifdef Nero
#include "Deb.h"
#else
#define debug(...)
#endif
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
vector<int> s(n), e(n);
for (int i = 0; i < n; ++i) {
cin >> s[i] >> e[i];
}
int ans = n + 1;
for (int mask = 1; mask < (1 << n); ++mask) {
vector<pair<int, int>> ranges;
for (int i = 0; i < n; ++i) {
if (mask >> i & 1) {
if (s[i] <= e[i]) {
ranges.push_back({s[i], e[i]});
} else {
ranges.push_back({s[i], m - 1});
ranges.push_back({0, e[i]});
}
}
}
bool ok = true;
sort(ranges.begin(), ranges.end());
int mx = 0;
for (int i = 0; i < (int) ranges.size(); ++i) {
auto [l, r] = ranges[i];
if (mx < l) {
ok = false;
break;
}
mx = max(mx, r);
}
ok &= mx == m - 1;
if (ok) {
ans = min(ans, __builtin_popcount(mask));
}
}
cout << (ans > n ? -1 : ans) << '\n';
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |