Submission #670923

#	Time	Username	Problem	Language	Result	Execution time	Memory
670923		Kahou	Plus Minus (BOI17_plusminus)	C++14	100 / 100	119 ms	8256 KiB

plusminus

/* In the name of God, aka Allah */
// let this be mytemp.cpp
#include<bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define endl '\n'
#define mk make_pair
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int mod = 1e9+ 7;
int add(int a, int b) {
	a += b;
	if (a >= mod) a -= mod;
	if (a < 0) a += mod;
	return a;
}
int mul(int a, int b) {
	return 1ll*a*b%mod;
}
int pw(int a, int b) {
	int out = 1;
	while (b) {
		if (b&1) out = mul(out, a);
		a = mul(a, a);
		b>>=1;
	}
	return out;
}
const int N = 1e5 + 50;
int n, m, k;
pii A[N];
int B[N];
map<int, int> mp;

int f(int i) {
	return (A[i].S&1)^B[i];
}
void solve() {
	cin >> n >> m >> k;
	for (int i = 1; i <= k; i++) {
		char c;
		cin >> c;
		cin >> A[i].F >> A[i].S;
		B[i] = (c == '+');
	}
	if (k == 0) return cout << add(add(pw(2, n), pw(2, m)), -2) << endl, void();
	
	bool gd = 1;
	bool s = (A[1].F^A[1].S^B[1])&1;
	for (int i = 1; i <= k; i++) {
		gd = gd&&(((A[i].F^A[i].S^B[i])&1) == s);
	}

	int ans = 0;
	bool bd = 0;

	int cnt = n;

	for (int i = 1; i <= k; i++) {
		cnt -= (mp.find(A[i].F) == mp.end());

		if (mp.find(A[i].F) != mp.end()) {
			bd = bd||(mp[A[i].F] != f(i));
		}
		mp[A[i].F] = f(i);
	}

	if (!bd) {
		ans = add(ans, pw(2, cnt)-gd);
	}

	for (int i = 1; i <= k; i++) swap(A[i].F, A[i].S);


	mp.clear();
	s = f(1);
	cnt = m;
	bd = 0;

	for (int i = 1; i <= k; i++) {
		cnt -= (mp.find(A[i].F) == mp.end());
		
		if (mp.find(A[i].F) != mp.end()) {
			bd = bd||(mp[A[i].F] != f(i));
		}
		mp[A[i].F] = f(i);
	}
	if (!bd) {
		ans = add(ans, pw(2, cnt)-gd);
	}
	ans += gd;
	cout << ans << endl;
}
int main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	solve();
	return 0;
}

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