Submission #712082

#	Time	Username	Problem	Language	Result	Execution time	Memory
712082		Sohsoh84	Plus Minus (BOI17_plusminus)	C++17	100 / 100	213 ms	24332 KiB

plusminus

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pll;

#define all(x)			(x).begin(),(x).end()
#define X			first
#define Y			second
#define sep			' '
#define endl			'\n'
#define debug(x)		cerr << #x << ": " <<  x << endl;

const ll MAXN = 1e6 + 10;
const ll MOD = 1e9 + 7;

inline ll poww(ll a, ll b) {
	ll ans = 1;
	while (b) {
		if (b & 1) ans = ans * a % MOD;
		b >>= 1;
		a = a * a % MOD;
	}

	return ans;
}

int n, m, k;
map<int, vector<int>> RV, CV;
bool f1 = true, f2 = true;

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> n >> m >> k;

	while (k--) {
		char tc;
		int r, c, s;
		cin >> tc >> r >> c;
		s = (tc == '+' ? 1 : 0);

		int w = ((r + c) & 1);
		f1 &= bool(s ^ w);
		f2 &= bool(s ^ (1 - w));
	
		RV[r].push_back(c - s);
		CV[c].push_back(r - s);
	}
	
	ll ans = 0;
	bool rflag = true;
	for (auto [_, vec] : RV) {
		for (int e : vec)
			if ((e ^ vec.front()) & 1)
				rflag = false;
	}

	if (rflag) ans += poww(2, n - int(RV.size()));

	bool cflag = true;
	for (auto [_, vec] : CV) {
		for (int e : vec)
			if ((e ^ vec.front()) & 1)
				cflag = false;
	}

	if (cflag) ans += poww(2,  m - int(CV.size()));
	
	ans += MOD;
	ans -= f1;
	ans -= f2;

	cout << ans % MOD << endl;
	return 0;
}

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