Submission #550990

#	Time	Username	Problem	Language	Result	Execution time	Memory
550990		blue	Plus Minus (BOI17_plusminus)	C++17	100 / 100	54 ms	2808 KiB

plusminus

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
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;

	vector<int> rows, cols;

	vector<pii> R, C;
	
	vi Z(2, 0);

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

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

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

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

		R.push_back({x, a ^ (y % 2)});
		C.push_back({y, a ^ (x % 2)});
		Z[a ^ (x % 2) ^ (y % 2)] = 1;
	}

	sort(rows.begin(), rows.end());
	rows.erase(unique(rows.begin(), rows.end()), rows.end());

	sort(cols.begin(), cols.end());
	cols.erase(unique(cols.begin(), cols.end()), cols.end());

	sort(R.begin(), R.end());
	R.erase(unique(R.begin(), R.end()), R.end());

	sort(C.begin(), C.end());
	C.erase(unique(C.begin(), C.end()), C.end());

	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";

	int zct = Z[0] + Z[1];

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

	cout << res << '\n';

}

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