Submission #292798

#TimeUsernameProblemLanguageResultExecution timeMemory
292798BTheroPort Facility (JOI17_port_facility)C++17
10 / 100
794 ms8696 KiB
// chrono::system_clock::now().time_since_epoch().count() #include<bits/stdc++.h> #define pb push_back #define eb emplace_back #define mp make_pair #define fi first #define se second #define all(x) (x).begin(), (x).end() #define debug(x) cerr << #x << " = " << x << endl; using namespace std; typedef long long ll; typedef pair<int, int> pii; const int MAXN = (int)2e3 + 5; const int MOD = (int)1e9 + 7; int addMod(int a, int b, int m = MOD) { a += b; if (m <= a) { a -= m; } return a; } int mulMod(int a, int b, int m = MOD) { return a * 1ll * b % m; } vector<int> adj[MAXN]; int col[MAXN]; pii arr[MAXN]; int n; bool bit(int x, int p) { return x & (1 << p); } bool cmp(pii a, pii b) { return a.se < b.se; } bool dfs(int v) { for (int to : adj[v]) { if (col[to] == -1) { col[to] = 1 - col[v]; if (dfs(to)) { return 1; } } else if (col[to] == col[v]) { return 1; } } return 0; } void solve() { scanf("%d", &n); for (int i = 1; i <= n; ++i) { scanf("%d %d", &arr[i].fi, &arr[i].se); } sort(arr + 1, arr + n + 1, cmp); for (int i = 1; i <= n; ++i) { for (int j = i + 1; j <= n; ++j) { if (arr[i].fi < arr[j].fi && arr[i].se > arr[j].fi) { for (int k = j + 1; k <= n; ++k) { if (arr[j].fi < arr[k].fi && arr[j].se > arr[k].fi) { if (arr[i].fi < arr[k].fi && arr[i].se > arr[k].fi) { printf("0\n"); return; } } } adj[i].pb(j); adj[j].pb(i); } } } fill(col + 1, col + n + 1, -1); int ans = 1; for (int i = 1; i <= n; ++i) { if (col[i] == -1) { col[i] = 0; assert(!dfs(i)); ans = addMod(ans, ans); } } printf("%d\n", ans); } int main() { int tt = 1; while (tt--) { solve(); } return 0; }

Compilation message (stderr)

port_facility.cpp: In function 'void solve()':
port_facility.cpp:65:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   65 |   scanf("%d", &n);
      |   ~~~~~^~~~~~~~~~
port_facility.cpp:68:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   68 |     scanf("%d %d", &arr[i].fi, &arr[i].se);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...