oj.uz

Submission #550989

# Submission time Handle Problem Language Result Execution time Memory
550989 2022-04-19T16:08:18 Z blue Plus Minus (BOI17_plusminus) C++17
0 / 100
 0 ms 212 KB 
#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());
	cols.erase(unique(cols.begin(), cols.end()), cols.end());
	R.erase(unique(R.begin(), R.end()), R.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
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 0 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 0 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 0 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -