#include <bits/stdc++.h>
using namespace std;
int modulo = 1e9 + 7;
int n,m,k;
int lgpow(int x, int y)
{
int z = 1;
while (y != 0)
{
if (y % 2 == 1)
z = 1ll * z * x % modulo;
x = 1ll * x * x % modulo;
y /= 2;
}
return z;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> n >> m >> k;
bool nah1 = false, nah2 = false;
set<int> ff1, ff2;
map<int,int> lin, col;
bool could_be_chessboard_1 = true, could_be_chessboard_2 = true;
for (int i = 1; i <= k; i++)
{
char spin;
int x,y;
cin >> spin >> x >> y;
ff1.insert(x);
ff2.insert(y);
if (spin == '+' and (x + y) % 2 == 0)
could_be_chessboard_1 = false;
if (spin == '+' and (x + y) % 2 == 1)
could_be_chessboard_2 = false;
if (spin == '-' and (x + y) % 2 == 0)
could_be_chessboard_2 = false;
if (spin == '-' and (x + y) % 2 == 1)
could_be_chessboard_1 = false;
if (spin == '+')
{
if (lin[x] != 0)
{
if (lin[x] != 1 + y % 2)
{
nah1 = true;
}
}
else
lin[x] = 1 + y % 2;
}
else
{
if (lin[x] != 0)
{
if (lin[x] != 1 + (y - 1) % 2)
{
nah1 = true;
}
}
else
lin[x] = 1 + (y - 1) % 2;
}
if (spin == '+')
{
if (col[y] != 0)
{
if (col[y] != 1 + x % 2)
{
nah2 = true;
}
}
else
col[y] = 1 + x % 2;
}
else
{
if (col[y] != 0)
{
if (col[y] != 1 + (x - 1) % 2)
{
nah2 = true;
}
}
else
col[y] = 1 + (x - 1) % 2;
}
}
int ans = 0;
if (!nah1)
ans += lgpow(2, n - (int)ff1.size());
if (!nah2)
ans += lgpow(2, m - (int)ff2.size());
if (could_be_chessboard_1)
ans--;
if (could_be_chessboard_2)
ans--;
cout << ans % modulo;
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
600 KB |
Output is correct |
2 |
Correct |
1 ms |
344 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 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 |
1 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
600 KB |
Output is correct |
2 |
Correct |
1 ms |
344 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 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 |
1 ms |
348 KB |
Output is correct |
11 |
Correct |
1 ms |
348 KB |
Output is correct |
12 |
Correct |
0 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 |
40 ms |
1512 KB |
Output is correct |
17 |
Correct |
41 ms |
1392 KB |
Output is correct |
18 |
Correct |
41 ms |
1372 KB |
Output is correct |
19 |
Correct |
40 ms |
1360 KB |
Output is correct |
20 |
Correct |
41 ms |
1508 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
600 KB |
Output is correct |
2 |
Correct |
1 ms |
344 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 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 |
1 ms |
348 KB |
Output is correct |
11 |
Correct |
1 ms |
348 KB |
Output is correct |
12 |
Correct |
0 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 |
40 ms |
1512 KB |
Output is correct |
17 |
Correct |
41 ms |
1392 KB |
Output is correct |
18 |
Correct |
41 ms |
1372 KB |
Output is correct |
19 |
Correct |
40 ms |
1360 KB |
Output is correct |
20 |
Correct |
41 ms |
1508 KB |
Output is correct |
21 |
Correct |
113 ms |
12984 KB |
Output is correct |
22 |
Correct |
0 ms |
344 KB |
Output is correct |
23 |
Correct |
109 ms |
12976 KB |
Output is correct |
24 |
Correct |
107 ms |
12880 KB |
Output is correct |
25 |
Correct |
110 ms |
12880 KB |
Output is correct |
26 |
Correct |
128 ms |
17672 KB |
Output is correct |
27 |
Correct |
112 ms |
17744 KB |
Output is correct |
28 |
Correct |
112 ms |
17860 KB |
Output is correct |
29 |
Correct |
120 ms |
17748 KB |
Output is correct |
30 |
Correct |
144 ms |
21332 KB |
Output is correct |