# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
130421 | 2019-07-15T07:44:30 Z | PeppaPig | Plus Minus (BOI17_plusminus) | C++14 | 165 ms | 6556 KB |
#include <bits/stdc++.h> #define long long long #define pii pair<int, int> #define x first #define y second using namespace std; const int M = 1e9+7; long modpow(long a, long b) { long ret = 1; for( ; b; b >>= 1) { if(b & 1) ret = (ret * a) % M; a = (a * a) % M; } return ret; } int n, m, k, valid; long ans; void solve(int sz, vector<int> &x, vector<int> &y, vector<int> &val) { map<int, int> mp; for(int i = 0; i < x.size(); i++) { int now = x[i], f = val[i]; if(y[i] % 2 == 0) f ^= 1; if(!mp.count(now)) mp[now] = f; else if(mp[now] != f) return; } ans = (ans + modpow(2, sz - (int)mp.size())) % M; int b = -1; for(pii p : mp) { int now = ((p.x & 1) == p.y); if(b == -1) b = now; else if(b != now) return; } ++valid; } vector<int> x, y, val; int main() { scanf("%d %d %d", &n, &m, &k); if(k == 0) return !printf("%lld\n", (modpow(2, n) + modpow(2, m) - 2 + M) % M); for(int i = 1; i <= k; i++) { int a, b; char c; scanf(" %c %d %d", &c, &a, &b); x.emplace_back(a), y.emplace_back(b); val.emplace_back(c == '+'); } solve(n, x, y, val), solve(m, y, x, val); if(valid == 2) ans = (ans - 1 + M) % M; printf("%lld\n", ans); return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 256 KB | Output is correct |
2 | Correct | 2 ms | 256 KB | Output is correct |
3 | Correct | 2 ms | 256 KB | Output is correct |
4 | Correct | 2 ms | 256 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 | 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 | 256 KB | Output is correct |
2 | Correct | 2 ms | 256 KB | Output is correct |
3 | Correct | 2 ms | 256 KB | Output is correct |
4 | Correct | 2 ms | 256 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 | 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 | 3 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 | 2 ms | 376 KB | Output is correct |
16 | Correct | 30 ms | 2140 KB | Output is correct |
17 | Correct | 29 ms | 2020 KB | Output is correct |
18 | Correct | 29 ms | 2024 KB | Output is correct |
19 | Correct | 59 ms | 2060 KB | Output is correct |
20 | Correct | 59 ms | 2024 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 256 KB | Output is correct |
2 | Correct | 2 ms | 256 KB | Output is correct |
3 | Correct | 2 ms | 256 KB | Output is correct |
4 | Correct | 2 ms | 256 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 | 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 | 3 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 | 2 ms | 376 KB | Output is correct |
16 | Correct | 30 ms | 2140 KB | Output is correct |
17 | Correct | 29 ms | 2020 KB | Output is correct |
18 | Correct | 29 ms | 2024 KB | Output is correct |
19 | Correct | 59 ms | 2060 KB | Output is correct |
20 | Correct | 59 ms | 2024 KB | Output is correct |
21 | Correct | 132 ms | 4724 KB | Output is correct |
22 | Correct | 2 ms | 376 KB | Output is correct |
23 | Correct | 33 ms | 2024 KB | Output is correct |
24 | Correct | 33 ms | 2024 KB | Output is correct |
25 | Correct | 35 ms | 2024 KB | Output is correct |
26 | Correct | 82 ms | 4636 KB | Output is correct |
27 | Correct | 84 ms | 4180 KB | Output is correct |
28 | Correct | 119 ms | 4784 KB | Output is correct |
29 | Correct | 139 ms | 5608 KB | Output is correct |
30 | Correct | 165 ms | 6556 KB | Output is correct |