Submission #1129691

#	Time	Username	Problem	Language	Result	Execution time	Memory
1129691		Muhammet	Plus Minus (BOI17_plusminus)	C++20	54 / 100	389 ms	589824 KiB

plusminus

#include "bits/stdc++.h"

using namespace std;

#define ll long long

const int M = 1e9+7;

int n, m, k, ans;

map <int,int> mpr, mpc;

ll f(int x){
	if(x == 0) return 1;
	if(x % 2 == 0) return (f(x/2) * f(x/2) * 1LL) % M;
	else return (f(x/2) * f(x/2) * 2 * 1LL) % M;
}

int main(){
	ios::sync_with_stdio(false); cin.tie(nullptr);

	cin >> n >> m >> k;
	int n1 = n, m1 = m;
	vector <vector <int>> ab(n+1, vector <int> (m+1,-1));
	bool tr = 0, tr1 = 0;
	for(int i = 1; i <= k; i++){
		char c;
		int x, y;
		cin >> c >> x >> y;
		int a = (c == '+' ? 1 : 0);
		ab[x][y] = a;
		if(!(y % 2)) a = (a+1)%2;
		a++;
		if(mpr[x] == 0) mpr[x] = a, n--;
		else {
			if(mpr[x] != a) tr = 1;
		}
		a = (c == '+' ? 1 : 0);
		if(!(x % 2)) a = (a+1)%2;
		a++;
		if(mpc[y] == 0) mpc[y] = a, m--;
		else {
			if(mpc[y] != a) tr1 = 1;
		}
	}
	ll ans = 0;
	if(!tr) ans += f(n);
	ans %= M;
	if(!tr1) ans += f(m);
	ans %= M;
	int b1 = 1, b2 = 1;
	bool t;
	for(int i = 1; i <= n1; i++){
		t = (i % 2);
		for(int j = 1; j <= m1; j++){
			if(~ab[i][j] and ab[i][j] != t) b1 = 0;
			t = (1-t);
		}
	}
	for(int i = 1; i <= n1; i++){
		t = (i%2)^1;
		for(int j = 1; j <= m1; j++){
			if(~ab[i][j] and ab[i][j] != t) b2 = 0;
			t = (1-t);
		}
	}
	cout << ans-(b1+b2) << '\n';
}

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