#include<bits/stdc++.h>
using namespace std;
using ll = long long;
typedef pair<int, int> pii;
constexpr ll mod = 1e9 + 7;
ll binary_exp(ll base, ll power)
{
if (power == 0) return 1;
ll output = 1;
ll inc = 2;
for (int i = 0; i < 32; i++)
{
if (power & (1 << i)) {
output *= inc;
output %= mod;
}
inc *= inc;
inc %= mod;
}
// cout << base << " " << power << " " << output <<"\n";
return output;
}
struct tri{
int x, y;
bool b;
void s()
{
swap(x, y);
}
bool operator<(const tri &t) const {
if (x == t.x) return y < t.y;
return x < t.x;
}
} ;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
ll n, m, k;
cin >> n >> m >> k;
ll output = 0;
if (k == 0)
{
output = binary_exp(2, n) + binary_exp(2, m) - 2;
output %= mod;
cout << output << "\n";
return 0;
}
vector <tri> v(k);
char c;
int a, b;
for (int i = 0; i < k; i++)
{
cin >> c >> a >> b;
v[i] = tri{b, a, (c == '+')};
}
bool direction[2] = { 0 };
for (int f = 0; f < 2; f++)
{
sort(v.begin(), v.end());
int lines = m;
tri last = { -1, -1, 0 };
for (tri t : v)
{
if (last.x == -1) {
lines--;
}
else if (t.x == last.x)
{
if (t.b == last.b)
{
if (abs(t.y - last.y) & 1) {direction[f] = 1; break;}
else continue;
} else {
if (abs(t.y - last.y) & 1) continue;
else {direction[f] = 1; break;}
}
} else {
lines--;
}
last = t;
}
if (!direction[f]) {
output += binary_exp(2, lines);
}
for (tri &t : v) t.s();
swap(m, n);
}
int l = -1;
bool removed = false;
if (!direction[0] && !direction[1]) {
removed = true;
for (tri t : v)
{
if (l == -1)
{
l = (t.x + t.y + t.b) & 1;
}
else {
if (((t.x + t.y + t.b) & 1) == l) continue;
else removed = false;
}
}
}
output -= removed;
output %= mod;
cout << output << "\n";
// cerr << direction[0] << " " << direction[1] << "\n";
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
8 |
Correct |
0 ms |
212 KB |
Output is correct |
9 |
Correct |
0 ms |
212 KB |
Output is correct |
10 |
Correct |
0 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
8 |
Correct |
0 ms |
212 KB |
Output is correct |
9 |
Correct |
0 ms |
212 KB |
Output is correct |
10 |
Correct |
0 ms |
212 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
0 ms |
212 KB |
Output is correct |
13 |
Correct |
0 ms |
212 KB |
Output is correct |
14 |
Correct |
1 ms |
328 KB |
Output is correct |
15 |
Correct |
1 ms |
340 KB |
Output is correct |
16 |
Correct |
34 ms |
2384 KB |
Output is correct |
17 |
Correct |
41 ms |
2392 KB |
Output is correct |
18 |
Correct |
35 ms |
2388 KB |
Output is correct |
19 |
Correct |
38 ms |
2376 KB |
Output is correct |
20 |
Correct |
35 ms |
2388 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
8 |
Correct |
0 ms |
212 KB |
Output is correct |
9 |
Correct |
0 ms |
212 KB |
Output is correct |
10 |
Correct |
0 ms |
212 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
0 ms |
212 KB |
Output is correct |
13 |
Correct |
0 ms |
212 KB |
Output is correct |
14 |
Correct |
1 ms |
328 KB |
Output is correct |
15 |
Correct |
1 ms |
340 KB |
Output is correct |
16 |
Correct |
34 ms |
2384 KB |
Output is correct |
17 |
Correct |
41 ms |
2392 KB |
Output is correct |
18 |
Correct |
35 ms |
2388 KB |
Output is correct |
19 |
Correct |
38 ms |
2376 KB |
Output is correct |
20 |
Correct |
35 ms |
2388 KB |
Output is correct |
21 |
Correct |
39 ms |
2764 KB |
Output is correct |
22 |
Correct |
1 ms |
212 KB |
Output is correct |
23 |
Correct |
34 ms |
2764 KB |
Output is correct |
24 |
Correct |
44 ms |
2760 KB |
Output is correct |
25 |
Correct |
37 ms |
2756 KB |
Output is correct |
26 |
Correct |
33 ms |
2960 KB |
Output is correct |
27 |
Correct |
32 ms |
2944 KB |
Output is correct |
28 |
Correct |
35 ms |
2952 KB |
Output is correct |
29 |
Correct |
31 ms |
3028 KB |
Output is correct |
30 |
Correct |
40 ms |
3528 KB |
Output is correct |