Submission #415283

#TimeUsernameProblemLanguageResultExecution timeMemory
415283BlagojcePlus Minus (BOI17_plusminus)C++11
100 / 100
75 ms11752 KiB
#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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...