oj.uz

Submission #415279

# Submission time Handle Problem Language Result Execution time Memory
415279 2021-05-31T19:28:59 Z Blagojce Plus Minus (BOI17_plusminus) C++11
0 / 100
 1 ms 320 KB 
#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;
		g.pb({});
		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; 
				}
			}
		}
		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
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 320 KB Output is correct
2 Correct 1 ms 268 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Incorrect 1 ms 204 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 320 KB Output is correct
2 Correct 1 ms 268 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Incorrect 1 ms 204 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 320 KB Output is correct
2 Correct 1 ms 268 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Incorrect 1 ms 204 KB Output isn't correct
6 Halted 0 ms 0 KB -