# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
132512 | 2019-07-19T05:29:16 Z | tlwpdus | Plus Minus (BOI17_plusminus) | C++11 | 67 ms | 1912 KB |
#include <bits/stdc++.h> #define x first #define y second using namespace std; typedef long long ll; typedef pair<int,int> pii; const ll MOD = 1e9+7; int n, m, k; pii arr[100100]; int sgn[100100]; int ord[100100]; ll po(ll a, ll n) { if (!n) return 1; ll t = po(a,n/2); return t*t%MOD*(n%2?a:1)%MOD; } ll solve() { iota(ord,ord+k,0); sort(ord,ord+k,[](int a, int b){return arr[a]<arr[b];}); int p = 0, mang = 0, num = (k?1:0); for (int i=0;i<k;i++) { if (arr[ord[i]].x==arr[ord[p]].x) { if ((arr[ord[i]].y^sgn[ord[i]])%2!=(arr[ord[p]].y^sgn[ord[p]])%2) mang=1; } else { p = i; num++; } } return mang?0:po(2,n-num); } int main() { scanf("%d%d%d",&n,&m,&k); for (int i=0;i<k;i++) { char c; int a, b; scanf(" %c%d%d",&c,&a,&b); sgn[i] = (c=='+'?1:0); arr[i] = {a,b}; } ll ans = solve(); swap(n,m); for (int i=0;i<k;i++) swap(arr[i].x,arr[i].y); ans += solve(); if (!k) ans+=MOD-2; else { int mang = 0; for (int i=0;i<k;i++) { if ((arr[i].x^arr[i].y^sgn[i])%2!=(arr[0].x^arr[0].y^sgn[0])%2) mang = 1; } if (!mang) ans+=MOD-1; } printf("%lld\n",ans%MOD); return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 376 KB | Output is correct |
2 | Correct | 2 ms | 376 KB | Output is correct |
3 | Correct | 2 ms | 376 KB | Output is correct |
4 | Correct | 2 ms | 376 KB | Output is correct |
5 | Correct | 2 ms | 256 KB | Output is correct |
6 | Correct | 2 ms | 376 KB | Output is correct |
7 | Correct | 2 ms | 376 KB | Output is correct |
8 | Correct | 2 ms | 376 KB | Output is correct |
9 | Correct | 2 ms | 376 KB | Output is correct |
10 | Correct | 2 ms | 376 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 376 KB | Output is correct |
2 | Correct | 2 ms | 376 KB | Output is correct |
3 | Correct | 2 ms | 376 KB | Output is correct |
4 | Correct | 2 ms | 376 KB | Output is correct |
5 | Correct | 2 ms | 256 KB | Output is correct |
6 | Correct | 2 ms | 376 KB | Output is correct |
7 | Correct | 2 ms | 376 KB | Output is correct |
8 | Correct | 2 ms | 376 KB | Output is correct |
9 | Correct | 2 ms | 376 KB | Output is correct |
10 | Correct | 2 ms | 376 KB | Output is correct |
11 | Correct | 2 ms | 376 KB | Output is correct |
12 | Correct | 2 ms | 256 KB | Output is correct |
13 | Correct | 2 ms | 376 KB | Output is correct |
14 | Correct | 2 ms | 376 KB | Output is correct |
15 | Correct | 3 ms | 376 KB | Output is correct |
16 | Correct | 60 ms | 1912 KB | Output is correct |
17 | Correct | 62 ms | 1912 KB | Output is correct |
18 | Correct | 58 ms | 1912 KB | Output is correct |
19 | Correct | 59 ms | 1912 KB | Output is correct |
20 | Correct | 58 ms | 1912 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 376 KB | Output is correct |
2 | Correct | 2 ms | 376 KB | Output is correct |
3 | Correct | 2 ms | 376 KB | Output is correct |
4 | Correct | 2 ms | 376 KB | Output is correct |
5 | Correct | 2 ms | 256 KB | Output is correct |
6 | Correct | 2 ms | 376 KB | Output is correct |
7 | Correct | 2 ms | 376 KB | Output is correct |
8 | Correct | 2 ms | 376 KB | Output is correct |
9 | Correct | 2 ms | 376 KB | Output is correct |
10 | Correct | 2 ms | 376 KB | Output is correct |
11 | Correct | 2 ms | 376 KB | Output is correct |
12 | Correct | 2 ms | 256 KB | Output is correct |
13 | Correct | 2 ms | 376 KB | Output is correct |
14 | Correct | 2 ms | 376 KB | Output is correct |
15 | Correct | 3 ms | 376 KB | Output is correct |
16 | Correct | 60 ms | 1912 KB | Output is correct |
17 | Correct | 62 ms | 1912 KB | Output is correct |
18 | Correct | 58 ms | 1912 KB | Output is correct |
19 | Correct | 59 ms | 1912 KB | Output is correct |
20 | Correct | 58 ms | 1912 KB | Output is correct |
21 | Correct | 60 ms | 1884 KB | Output is correct |
22 | Correct | 2 ms | 376 KB | Output is correct |
23 | Correct | 59 ms | 1884 KB | Output is correct |
24 | Correct | 59 ms | 1912 KB | Output is correct |
25 | Correct | 59 ms | 1912 KB | Output is correct |
26 | Correct | 55 ms | 1656 KB | Output is correct |
27 | Correct | 56 ms | 1656 KB | Output is correct |
28 | Correct | 58 ms | 1656 KB | Output is correct |
29 | Correct | 58 ms | 1660 KB | Output is correct |
30 | Correct | 67 ms | 1912 KB | Output is correct |