Submission #714595

#	Time	Username	Problem	Language	Result	Execution time	Memory
714595		parsadox2	Plus Minus (BOI17_plusminus)	C++14	100 / 100	578 ms	40008 KiB

plusminus

#include <bits/stdc++.h>
#define pb 		push_back
#define F		first
#define S 		second
#define debug(x)    cout << #x << "= " << x << ", "
#define ll 		long long
#define fast 		ios::sync_with_stdio(false), cin.tie(0),  cout.tie(0)
#define SZ(x)         (int) x.size()
#define wall 		cout << endl;
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int mod = 1e9 + 7;
map <int , bool> mp_c[2][2] , vis_c , vis_r , mp_r[2][2];
bool marked[2][2];

int mpo(int a , int b)
{
	if(b == 0)  return 1;
	int tmp = mpo(a , b >> 1);
	tmp = 1LL * tmp * tmp % mod;
	if(b & 1)  tmp = 1LL * tmp * a % mod;
	return tmp;
}

int32_t main()
{
	fast;
	int n , m , k;  cin >> n >> m >> k;
	int used_row = 0 , used_col = 0;
	bool shr = true , shc = true;
	while(k--)
	{
		char c;  int row , col;
		cin >> c >> row >> col;
		int val = (c == '-' ? 0 : 1);
		mp_r[val][(col & 1)][row] = true;
		mp_c[val][(row & 1)][col] = true;
		if(!vis_r[row])  used_row++;
		if(!vis_c[col])  used_col++;
		vis_r[row] = true;
		vis_c[col] = true;
		marked[val][((row + col) & 1)] = true;
		if(mp_r[val][(col & 1) ^ 1][row] || mp_r[(val ^ 1)][(col & 1)][row])  shr = false;
		if(mp_c[val][(row & 1) ^ 1][col] || mp_c[(val ^ 1)][(row & 1)][col])  shc = false;
	}
	int ans = 0;
	if(shr)  ans = (ans + mpo(2 , n - used_row)) % mod;
	if(shc)  ans = (ans + mpo(2 , m - used_col)) % mod;
	if(!marked[1][1] && !marked[0][0])  ans--;
	if(!marked[0][1] && !marked[1][0])  ans--;
	ans = (ans + mod) % mod;
	cout << ans << endl;
	return 0;
}

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