Submission #1116068

#	Time	Username	Problem	Language	Result	Execution time	Memory
1116068		kustizus	Plus Minus (BOI17_plusminus)	C++17	100 / 100	94 ms	8264 KiB

plusminus

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define fi first
#define se second
#define all(v) v.begin(), v.end()

const int K = 1e5, MOD = 1e9 + 7;
int n, m, k, x[K + 5], y[K + 5];
map <int,int> mp;
char ty[K + 5];

int binpow(int a, int b){
	int ans = 1;
	while (b){
		if (b & 1) ans = ans * a % MOD;
		a = a * a % MOD;
		b /= 2;
	}
	return ans;
}

void solve(){
	bool ok = true;
 	cin >> n >> m >> k;
 	for (int i = 1; i <= k; ++i){
 		cin >> ty[i] >> x[i] >> y[i];
 		int val;
 		if ((ty[i] == '-') == (x[i] & 1)) val = 0;
 		else val = 1;
 		if (mp.count(y[i])){
 			if (mp[y[i]] != val) ok = false;
 		}
 		else mp[y[i]] = val;
 	}
 	int ans = 0;
 	if (ok){
 		int x = m - (int)mp.size();
 		ans = binpow(2, x);
 		if (!k) ans -= 2;
 		else{
	 		int x = 0, y = 0;
 			for (pair <int,int> o : mp)
 				if (o.fi % 2 == o.se % 2) ++x;
 				else ++y;
 			if (!x) --ans;
 			else if (!y) --ans;
 		}
 	}
 	mp.clear();
 	ok = true;
 	for (int i = 1; i <= k; ++i){
 		int val;
 		if ((ty[i] == '-') == (y[i] & 1)) val = 0;
 		else val = 1;
 		if (mp.count(x[i])){
 			if (mp[x[i]] != val) ok = false;
 		}
 		else mp[x[i]] = val;
 	}
 	if (ok) ans += binpow(2, n - mp.size());
 	cout << (ans % MOD + MOD) % MOD;
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    // freopen("file.inp", "r", stdin);
    // freopen("file.out", "w", stdout);
    int tt = 1;
    // cin >> tt;
    while (tt--){
        solve();
    }
}

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