제출 #415283

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
415283		Blagojce	Plus Minus (BOI17_plusminus)	C++11	100 / 100	75 ms	11752 KiB

plusminus

#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();
}

• Subtask 1: 12 / 12
• Subtask 2: 42 / 42
• Subtask 3: 46 / 46