#include <iostream>
#include <algorithm>
#include <functional>
#include <random>
#include <cmath>
#include <vector>
#include <array>
#include <set>
#include <map>
#include <queue>
#include <cassert>
#include <string>
#include <bitset>
#include <numeric>
#include <iomanip>
#include <limits.h>
#include <tuple>
using namespace std;
#define rep(i,l,r) for(int i = l; i < (r); i++)
#define per(i,r,l) for(int i = r; i >= (l); i--)
#define sz(x) (int)size(x)
#define pb push_back
#define all(x) begin(x), end(x)
#define ff first
#define ss second
typedef long long ll;
typedef pair<int, int> pp;
const ll mod = 1e9+7, maxn = 2e5 + 5, inf = ll(1e9) + 5, lg = 20;
ll pw(ll a, ll b){
if(b == 0) return 1;
ll k = pw(a, b>>1ll);
return k*k%mod*(b&1ll?a:1ll)%mod;
}
map<int, vector<pair<int, bool>>> ver, hor;
int n, m, k;
vector<pair<bool, pp>> node;
int chess_state(){
if(k == 0) return 2;
for(auto[vl, p]: node) if(((vl^(p.ff + p.ss))&1) != ((node.back().ff^(node.back().ss.ff + node.back().ss.ss))&1)) return 0;
return 1;
}
int hor_state(){
int exp = -1;
bool dec = true;
int cnt = 0;
for(auto[y, v]: hor){
cnt++;
pair<int, bool> ex = v.back();
int s = ((y + ex.ff)&1)^ex.ss;
if(exp == -1) exp = s;
else if(s != exp) dec = false;
for(auto[x, vl]: v){
if((((x + y)&1)^vl) != s) return 0;
}
}
ll ans = pw(2, n - cnt);
if(dec) ans -= 1 + (k == 0);
return (ans + mod)%mod;
}
int ver_state(){
int exp = -1;
bool dec = true;
int cnt = 0;
for(auto[y, v]: ver){
cnt++;
pair<int, bool> ex = v.back();
int s = ((y + ex.ff)&1)^ex.ss;
if(exp == -1) exp = s;
else if(s != exp) dec = false;
for(auto[x, vl]: v){
if((((x + y)&1)^vl) != s) return 0;
}
}
ll ans = pw(2, m - cnt);
if(dec) ans -= 1 + (k == 0);
return (ans + mod)%mod;
}
int main(){
cin.tie(0) -> sync_with_stdio(0);
cin >> n >> m >> k; swap(n, m);
rep(i,0,k){
char s; cin >> s;
int x, y; cin >> x >> y;
ver[x].pb({y, s == '+'});
hor[y].pb({x, s == '+'});
node.pb({s == '+', {x, y}});
}
cout << (chess_state() + hor_state() + ver_state())%mod << '\n';
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
256 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
320 KB |
Output is correct |
5 |
Correct |
0 ms |
324 KB |
Output is correct |
6 |
Correct |
0 ms |
324 KB |
Output is correct |
7 |
Correct |
1 ms |
324 KB |
Output is correct |
8 |
Correct |
0 ms |
320 KB |
Output is correct |
9 |
Correct |
1 ms |
320 KB |
Output is correct |
10 |
Correct |
0 ms |
212 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
256 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
320 KB |
Output is correct |
5 |
Correct |
0 ms |
324 KB |
Output is correct |
6 |
Correct |
0 ms |
324 KB |
Output is correct |
7 |
Correct |
1 ms |
324 KB |
Output is correct |
8 |
Correct |
0 ms |
320 KB |
Output is correct |
9 |
Correct |
1 ms |
320 KB |
Output is correct |
10 |
Correct |
0 ms |
212 KB |
Output is correct |
11 |
Correct |
1 ms |
468 KB |
Output is correct |
12 |
Correct |
0 ms |
332 KB |
Output is correct |
13 |
Correct |
1 ms |
212 KB |
Output is correct |
14 |
Correct |
1 ms |
468 KB |
Output is correct |
15 |
Correct |
2 ms |
468 KB |
Output is correct |
16 |
Correct |
43 ms |
4932 KB |
Output is correct |
17 |
Correct |
41 ms |
4944 KB |
Output is correct |
18 |
Correct |
40 ms |
4884 KB |
Output is correct |
19 |
Correct |
34 ms |
4868 KB |
Output is correct |
20 |
Correct |
40 ms |
4888 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
256 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
320 KB |
Output is correct |
5 |
Correct |
0 ms |
324 KB |
Output is correct |
6 |
Correct |
0 ms |
324 KB |
Output is correct |
7 |
Correct |
1 ms |
324 KB |
Output is correct |
8 |
Correct |
0 ms |
320 KB |
Output is correct |
9 |
Correct |
1 ms |
320 KB |
Output is correct |
10 |
Correct |
0 ms |
212 KB |
Output is correct |
11 |
Correct |
1 ms |
468 KB |
Output is correct |
12 |
Correct |
0 ms |
332 KB |
Output is correct |
13 |
Correct |
1 ms |
212 KB |
Output is correct |
14 |
Correct |
1 ms |
468 KB |
Output is correct |
15 |
Correct |
2 ms |
468 KB |
Output is correct |
16 |
Correct |
43 ms |
4932 KB |
Output is correct |
17 |
Correct |
41 ms |
4944 KB |
Output is correct |
18 |
Correct |
40 ms |
4884 KB |
Output is correct |
19 |
Correct |
34 ms |
4868 KB |
Output is correct |
20 |
Correct |
40 ms |
4888 KB |
Output is correct |
21 |
Correct |
139 ms |
16192 KB |
Output is correct |
22 |
Correct |
1 ms |
212 KB |
Output is correct |
23 |
Correct |
170 ms |
16240 KB |
Output is correct |
24 |
Correct |
123 ms |
16240 KB |
Output is correct |
25 |
Correct |
126 ms |
16184 KB |
Output is correct |
26 |
Correct |
158 ms |
21332 KB |
Output is correct |
27 |
Correct |
162 ms |
21388 KB |
Output is correct |
28 |
Correct |
143 ms |
21376 KB |
Output is correct |
29 |
Correct |
147 ms |
21268 KB |
Output is correct |
30 |
Correct |
238 ms |
25468 KB |
Output is correct |