제출 #533859

#제출 시각아이디문제언어결과실행 시간메모리
533859sarePort Facility (JOI17_port_facility)C++17
22 / 100
6079 ms18936 KiB
//In the name of Allah :) #include <bits/stdc++.h> using namespace std; string to_string(char c) { return string(1,c); } string to_string(bool b) { return b ? "true" : "false"; } string to_string(const char* s) { return (string)s; } string to_string(string s) { return s; } template<class A> string to_string(complex<A> c) { stringstream ss; ss << c; return ss.str(); } string to_string(vector<bool> v) { string res = "{"; for(int i = 0; i < (int)v.size(); i++) res += char('0'+v[i]); res += "}"; return res; } template<size_t SZ> string to_string(bitset<SZ> b) { string res = ""; for(size_t i = 0; i < SZ; i++) res += char('0'+b[i]); return res; } template<class A, class B> string to_string(pair<A,B> p); template<class T> string to_string(T v) { // containers with begin(), end() bool fst = 1; string res = "{"; for (const auto& x: v) { if (!fst) res += ", "; fst = 0; res += to_string(x); } res += "}"; return res; } template<class A, class B> string to_string(pair<A,B> p) { return "("+to_string(p.first)+", "+to_string(p.second)+")"; } void DBG() { cerr << "]" << endl; } template<class H, class... T> void DBG(H h, T... t) { cerr << to_string(h); if (sizeof...(t)) cerr << ", "; DBG(t...); } #ifdef LOCAL // compile with -DLOCAL #define wis(...) cerr << "LINE(" << __LINE__ << ") -> [" << #__VA_ARGS__ << "] : [", DBG(__VA_ARGS__) #else #define wis(...) 0 #endif typedef long long ll; #define all(x) (x).begin(), (x).end() const int MAXN = 1e5 + 10, MOD = 1e9 + 7; vector<int> adj[MAXN]; pair<int, int> a[MAXN]; bitset<MAXN> mark; int color[MAXN]; bool bip = 1; void dfs (int v, int c) { mark[v] = 1; color[v] = c; for (int i : adj[v]) { if (mark[i]) { bip &= color[i] != c; } else { dfs(i, c ^ 1); } } } int main() { ios::sync_with_stdio(0); #ifndef LOCAL cin.tie(0); #endif int n; cin >> n; for (int i = 0; i < n; i++) { cin >> a[i].first >> a[i].second; } sort(a, a + n); for (int j = 0; j < n; j++) { for (int i = j + 1; i < n; i++) { if (a[i].first < a[j].second && a[i].second > a[j].second) { adj[i].push_back(j); adj[j].push_back(i); } if (a[i].first > a[j].second) { break; } } } int m = 0; for (int i = 0; i < n; i++) { if (!mark[i]) { dfs(i, 0); m++; } } if (bip == 0) { cout << 0 << '\n'; return 0; } int ans = 1; while (m--) { ans = ans + ans >= MOD ? ans + ans - MOD : ans + ans; } cout << ans << '\n'; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...