This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define fr(i, n, m) for(int i = (n); i < (m); i ++)
#define pb push_back
#define st first
#define nd second
#define pq priority_queue
#define all(x) begin(x), end(x)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pii;
const ll inf = 1e18;
const int i_inf = 1e9;
const ll mod = 1e9+7;
mt19937 _rand(time(NULL));
const int mxn = 2e5;
ll modpow(int x, int n){
if(n == 0) return 1;
ll u = modpow(x, n/2);
u = (u*u)%mod;
if(n%2) u = (u*x)%mod;
return u;
}
ll h, w;
int n;
struct electron{
bool spin;
ll r, c;
};
vector<electron> v;
void solve(){
cin >> h >> w >> n;
v.resize(n);
fr(i, 0, n){
char t;
cin >> t;
v[i].spin = t == '+';
cin >> v[i].r >> v[i].c;
}
ll ans = 0;
int valid = 0;
fr(t, 0, 2){
sort(all(v), [](const electron &i, const electron &j){
return i.r < j.r;
});
vector<vector<electron> > g;
int active_row = 0;
int row_cnt = 0;
for(auto u : v){
if(u.r != active_row){
row_cnt ++;
active_row = u.r;
g.pb({});
}
g.back().pb(u);
}
bool ok = true;
for(auto u : g){
int spin[2] = {-1, -1};
for(auto e : u){
int parity = e.c % 2;
if(spin[parity] == -1){
spin[parity] = e.spin;
}
else{
ok &= spin[parity] == (int)e.spin;
}
}
ok &= !(spin[0] == spin[1]);
}
if(ok){
++valid;
ans += modpow(2, h-row_cnt);
ans %= mod;
}
if(t == 0){
fr(i, 0, n){
swap(v[i].r, v[i].c);
}
swap(h, w);
}
}
//special case : checkboard
if(valid == 2){
fr(t, 0, 2){
bool ok = true;
for(auto u : v){
int p = (u.r+u.c)%2;
ok &= (p^t) == (int)u.spin;
}
if(ok){
--ans;
}
}
if(ans < 0) ans += mod;
}
cout<<ans<<endl;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
solve();
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |