Submission #550988

#	Time	Username	Problem	Language	Result	Execution time	Memory
550988		blue	Plus Minus (BOI17_plusminus)	C++17	100 / 100	189 ms	21100 KiB

plusminus

#include <iostream>
#include <vector>
#include <set>
using namespace std;

using vi = vector<int>;
using ll = long long;
using pii = pair<int, int>;
#define sz(x) int(x.size())

const ll mod = 1'000'000'007LL;

ll sq(ll a)
{
	return (a*a)%mod;
}

ll mul(ll a, ll b)
{
	return (a*b)%mod;
}

ll pow(ll b, ll e)
{
	if(e == 0) return 1;
	else if(e % 2 == 0) return sq(pow(b, e/2));
	else return mul(b, pow(b, e-1));
}

ll ad(ll a, ll b)
{
	return (a+b)%mod;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	int N, M, K;
	cin >> N >> M >> K;

	set<int> rows, cols;

	set<pii> R, C;
	set<int> Z;

	for(int k = 1; k <= K; k++)
	{
		char z;
		cin >> z;

		int a = (z == '+');

		int x, y;
		cin >> x >> y;

		rows.insert(x);
		cols.insert(y);

		R.insert({x, a ^ (y % 2)});
		C.insert({y, a ^ (x % 2)});
		Z.insert(a ^ (x % 2) ^ (y % 2));
	}

	ll res = 0;

	// cerr << sz(rows) << ' ' << sz(cols) << '\n';


	if(sz(R) == sz(rows))
	{
		res = ad(res, pow(2, N - sz(rows)));
	}

	if(sz(C) == sz(cols))
	{
		res = ad(res, pow(2, M - sz(cols)));
	}
	// cerr << "\n";

	if(sz(Z) <= 1)
	{
		res = (res + mod - 1) % mod;
	}
	if(sz(Z) <= 0)
	{
		res = (res + mod - 1) % mod;
	}

	cout << res << '\n';

}

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