Submission #1211096

#TimeUsernameProblemLanguageResultExecution timeMemory
1211096madamadam3Port Facility (JOI17_port_facility)C++20
22 / 100
6091 ms32836 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; struct Event { int time, box_id; bool is_remove; const bool operator<(const Event &other) { return time < other.time; } }; const int MAXN = 1'000'001; const int MOD = 1'000'000'007; int n; int A[MAXN], B[MAXN]; vector<Event> events; ll modexp(ll a, ll p) { if (p == 0) return 1; if (p == 1) return a; ll ans = modexp(a, p / 2); ans %= MOD; ans *= ans; ans %= MOD; if (p % 2 == 1) ans *= a; ans %= MOD; return ans % MOD; } void solve() { int ways = 1; vector<vector<int>> crossings(n, vector<int>()); // had this idea previously to precompute crossings js was trying to brute force first for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { int ci = i, cj = j; if (A[cj] < A[ci]) swap(ci, cj); if (!(A[ci] < A[cj] && A[cj] < B[ci] && B[ci] < B[cj])) continue; crossings[ci].push_back(cj); crossings[cj].push_back(ci); } } vector<int> group(n, -1); int cmps = 0; // push the constraints down the group (ie. each incompatible thing on a different side) for (int i = 0; i < n; i++) { if (group[i] != -1) continue; group[i] = 1; cmps++; queue<int> q; q.push(i); while (!q.empty()) { int cur = q.front(); q.pop(); for (auto &restriction : crossings[cur]) { if (group[restriction] == -1) { group[restriction] = group[cur] == 1 ? 2 : 1; // push down the constraint q.push(restriction); } else if (group[restriction] == group[cur]) { // inconsistency, need to break cout << 0; return; } } } } ways = modexp(2, cmps); // either group 1 in A g2 B or g1 B g2 A so 2 ways for each cmp cout << ways; } signed main() { cin.tie(0)->sync_with_stdio(0); cin >> n; for (int i = 0; i < n; i++) { cin >> A[i] >> B[i]; } for (int i = 0; i < n; i++) { events.push_back(Event {A[i], i, false}); events.push_back(Event {B[i], i, true}); } sort(events.begin(), events.end()); solve(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...