Submission #1254102

#	Time	Username	Problem	Language	Result	Execution time	Memory
1254102		kaiboy	Plus Minus (BOI17_plusminus)	C++20	100 / 100	29 ms	1864 KiB

plusminus

#include <algorithm>
#include <iostream>

using namespace std;

const int  N = 100000;
const int MD = 1000000007;
const int V2 = (MD + 1) / 2;

int aa[N], xx[N], yy[N], ii[N];

long long power(long long a, int k) {
	long long p = 1;
	for ( ; k; k >>= 1) {
		if (k & 1)
			p = p * a % MD;
		a = a * a % MD;
	}
	return p;
}

int main() {
	ios_base::sync_with_stdio(false), cin.tie(NULL);
	int x_, y_, n; cin >> x_ >> y_ >> n;
	for (int i = 0; i < n; i++) {
		char c; int x, y; cin >> c >> x >> y, x--, y--;
		aa[i] = c == '-', xx[i] = x, yy[i] = y, ii[i] = i;
	}
	int ans = 0;
	for (int z = 0; z < 2; z++) {
		sort(ii, ii + n, [] (int i, int j) { return xx[i] < xx[j]; });
		long long p = power(2, x_); bool dbl = true;
		for (int h = 0, g; h < n; h = g) {
			int i = ii[h], j, x = xx[i], a = aa[i] ^ yy[i] & 1;
			bool yes = true;
			for (g = h + 1; g < n && xx[j = ii[g]] == x; g++)
				if ((aa[j] ^ yy[j] & 1) != a) {
					yes = false;
					break;
				}
			if (!yes) {
				p = 0;
				dbl = false;
				break;
			}
			p = p * V2 % MD;
			if ((a ^ x & 1) != z)
				dbl = false;
		}
		ans = (ans + p) % MD;
		if (dbl)
			ans = (ans - 1 + MD) % MD;
		swap(x_, y_);
		for (int i = 0; i < n; i++)
			swap(xx[i], yy[i]);
	}
	cout << ans << '\n';
	return 0;
}

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