# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
132720 | 2019-07-19T11:50:50 Z | youngyojun | Plus Minus (BOI17_plusminus) | C++11 | 66 ms | 3704 KB |
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int MOD = 1000000007; const int MAXN = 100055; ll pw(ll n, ll k) { ll r = 1; for(; k; k >>= 1) { if(k&1) r = n * r % MOD; n = n * n % MOD; } return r; } int O[MAXN]; int A[MAXN], B[MAXN]; bitset<MAXN> C; ll Ans; int H, W, N; void process() { iota(O, O+N+1, 0); sort(O+1, O+N+1, [&](int a, int b) { return A[a] < A[b]; }); int cnt = 0; for(int s = 1, e; s <= N; cnt++, s = e) { for(e = s+1; e <= N && A[O[e]] == A[O[s]]; e++); bool isOdd = false, isEven = false; for(int oi = s, i, t; oi < e; oi++) { i = O[oi]; t = A[i] + B[i] + (C[i] ? 1 : 0); ((t&1) ? isOdd : isEven) = true; } if(isOdd && isEven) return; } Ans += pw(2, H-cnt); if(MOD <= Ans) Ans -= MOD; } void minusOne() { bool isOdd = false, isEven = false; for(int i = 1, t; i <= N; i++) { t = A[i] + B[i] + (C[i] ? 1 : 0); ((t&1) ? isOdd : isEven) = true; } if(isOdd != isEven) Ans--; if(Ans < 0) Ans = MOD-1; } int main() { scanf("%d%d%d", &H, &W, &N); for(int i = 1; i <= N; i++) { char c; scanf(" %c%d%d", &c, &A[i], &B[i]); C[i] = '+' == c; } if(!N) { cout << (pw(2, H) + pw(2, W) - 2) % MOD << endl; return 0; } process(); swap(H, W); for(int i = 1; i <= N; i++) swap(A[i], B[i]); process(); minusOne(); cout << Ans << endl; return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 376 KB | Output is correct |
2 | Correct | 3 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 | 376 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 | 380 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 | 3 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 | 376 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 | 380 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 | 3 ms | 376 KB | Output is correct |
15 | Correct | 2 ms | 376 KB | Output is correct |
16 | Correct | 44 ms | 2476 KB | Output is correct |
17 | Correct | 43 ms | 2552 KB | Output is correct |
18 | Correct | 43 ms | 2424 KB | Output is correct |
19 | Correct | 45 ms | 2428 KB | Output is correct |
20 | Correct | 45 ms | 2424 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 376 KB | Output is correct |
2 | Correct | 3 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 | 376 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 | 380 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 | 3 ms | 376 KB | Output is correct |
15 | Correct | 2 ms | 376 KB | Output is correct |
16 | Correct | 44 ms | 2476 KB | Output is correct |
17 | Correct | 43 ms | 2552 KB | Output is correct |
18 | Correct | 43 ms | 2424 KB | Output is correct |
19 | Correct | 45 ms | 2428 KB | Output is correct |
20 | Correct | 45 ms | 2424 KB | Output is correct |
21 | Correct | 56 ms | 2932 KB | Output is correct |
22 | Correct | 2 ms | 256 KB | Output is correct |
23 | Correct | 53 ms | 2780 KB | Output is correct |
24 | Correct | 52 ms | 2936 KB | Output is correct |
25 | Correct | 53 ms | 2808 KB | Output is correct |
26 | Correct | 55 ms | 3064 KB | Output is correct |
27 | Correct | 54 ms | 3064 KB | Output is correct |
28 | Correct | 55 ms | 3064 KB | Output is correct |
29 | Correct | 55 ms | 3108 KB | Output is correct |
30 | Correct | 66 ms | 3704 KB | Output is correct |