#include <bits/stdc++.h>
using namespace std;
#define int long long
#define arr array
#define vct vector
#define hmap unordered_map
#define pii pair<int, int>
const int MX_N = 1e5 + 5, MD = 1e9 + 7;
int r, c, n;
arr<int, MX_N> vl;
arr<pii, MX_N> ps;
int md(int x) { return (x + MD) % MD; }
int expn(int x, int y) {
if (y == 0) return 1;
int hlf = expn(x, y / 2);
int ans = md(hlf * hlf);
if (y % 2 == 1) ans = md(ans * x);
return ans;
}
int flp(int x) { return ((x % 2 == 0) ? 1 : -1); }
int slv(int rw, int cl, int x, int y, int z) { // {1, 1}, {rw, 1}, {1, cl}
return flp(rw + cl + 1) * x + flp(cl + 1) * y + flp(rw + 1) * z;
}
int slv_rw(int rw, int cl, int x, int y, int z) { // {rw, cl}, {1, 1}, {1, cl}
return flp(cl + 1) * (x - flp(rw + cl + 1) * y - flp(rw + 1) * z);
}
int slv_cl(int rw, int cl, int x, int y, int z) { // {rw, cl}, {1, 1}, {rw, 1}
return flp(rw + 1) * (x - flp(rw + cl + 1) * y - flp(cl + 1) * z);
}
int chck(int x) {
for (int i = 1; i <= n; i++) {
int rw = ps[i].first, cl = ps[i].second;
if (rw == 1 && cl == 1) {
if (vl[i] != x) return false;
} else if (rw == 1) {
if (vl[i] != flp(cl + 1) * x) return false;
} else if (cl == 1) {
if (vl[i] != flp(rw + 1) * x) return false;
} else if (vl[i] != slv(rw, cl, x, flp(rw + 1) * x, flp(cl + 1) * x)) return false;
}
return true;
}
int cmp() {
int ans = 0;
for (int x : {-1, 1}) {
for (bool is_rw : {true, false}) {
bool hlt = false;
for (int i = 1; i <= n; i++) {
int rw = ps[i].first, cl = ps[i].second;
if (is_rw && cl == 1 && vl[i] != flp(rw + 1) * x) hlt = true;
if (!is_rw && rw == 1 && vl[i] != flp(cl + 1) * x) hlt = true;
}
if (hlt) continue;
hmap<int, int> fxd = {{1, x}};
for (int i = 1; i <= n; i++) {
int rw = ps[i].first, cl = ps[i].second;
if (is_rw && rw == 1) fxd.insert({cl, vl[i]});
if (!is_rw && cl == 1) fxd.insert({rw, vl[i]});
}
for (int i = 1; i <= n; i++) {
int rw = ps[i].first, cl = ps[i].second;
if (min(rw, cl) == 1) continue;
if (is_rw && fxd.count(cl) && fxd[cl] != slv_cl(rw, cl, vl[i], x, flp(rw + 1) * x)) hlt = true;
if (!is_rw && fxd.count(rw) && fxd[rw] != slv_rw(rw, cl, vl[i], x, flp(cl + 1) * x)) hlt = true;
if (is_rw) fxd.insert({cl, slv_cl(rw, cl, vl[i], x, flp(rw + 1) * x)});
if (!is_rw) fxd.insert({rw, slv_rw(rw, cl, vl[i], x, flp(cl + 1) * x)});
}
if (hlt) continue;
int nw_ans = (is_rw) ? expn(2, c - fxd.size()) : expn(2, r - fxd.size());
ans = md(ans + nw_ans);
}
ans -= chck(x);
}
return ans;
}
signed main() {
// freopen("pls.in", "r", stdin);
cin >> r >> c >> n;
for (int i = 1; i <= n; i++) {
char x; cin >> x >> ps[i].first >> ps[i].second;
vl[i] = (x == '+') ? 1 : -1;
}
int ans = cmp();
cout << ans << endl;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
344 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
344 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
1 ms |
348 KB |
Output is correct |
12 |
Correct |
1 ms |
348 KB |
Output is correct |
13 |
Correct |
0 ms |
348 KB |
Output is correct |
14 |
Correct |
1 ms |
348 KB |
Output is correct |
15 |
Correct |
1 ms |
348 KB |
Output is correct |
16 |
Correct |
30 ms |
3668 KB |
Output is correct |
17 |
Correct |
29 ms |
3664 KB |
Output is correct |
18 |
Correct |
29 ms |
3544 KB |
Output is correct |
19 |
Correct |
34 ms |
3572 KB |
Output is correct |
20 |
Correct |
35 ms |
3648 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
344 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
1 ms |
348 KB |
Output is correct |
12 |
Correct |
1 ms |
348 KB |
Output is correct |
13 |
Correct |
0 ms |
348 KB |
Output is correct |
14 |
Correct |
1 ms |
348 KB |
Output is correct |
15 |
Correct |
1 ms |
348 KB |
Output is correct |
16 |
Correct |
30 ms |
3668 KB |
Output is correct |
17 |
Correct |
29 ms |
3664 KB |
Output is correct |
18 |
Correct |
29 ms |
3544 KB |
Output is correct |
19 |
Correct |
34 ms |
3572 KB |
Output is correct |
20 |
Correct |
35 ms |
3648 KB |
Output is correct |
21 |
Correct |
61 ms |
6652 KB |
Output is correct |
22 |
Correct |
0 ms |
348 KB |
Output is correct |
23 |
Correct |
52 ms |
6576 KB |
Output is correct |
24 |
Correct |
53 ms |
6516 KB |
Output is correct |
25 |
Correct |
70 ms |
6520 KB |
Output is correct |
26 |
Correct |
82 ms |
8088 KB |
Output is correct |
27 |
Correct |
83 ms |
8092 KB |
Output is correct |
28 |
Correct |
81 ms |
8200 KB |
Output is correct |
29 |
Correct |
90 ms |
8344 KB |
Output is correct |
30 |
Correct |
118 ms |
9724 KB |
Output is correct |