Submission #896108

#	Time	Username	Problem	Language	Result	Execution time	Memory
896108		AlphaMale06	Plus Minus (BOI17_plusminus)	C++14	0 / 100	0 ms	348 KiB

plusminus

#include <bits/stdc++.h>

/*
	Oce nas,
	koji si na nebesima,
	da se sveti ime Tvoje,
	da dodje carstvo Tvoje,
	da bude volja Tvoja,
	i na zemlji, kao i na nebu.
	
	Hleb nas nasusni daj nam danas,
	i oprosti nam dugove nase,
	kao sto i mi oprastamo duznicima svojim,
	i ne uvedi nas u iskusenje,
	no izbavi nas od zloga.
	
	Jer je Tvoje Carstvo,
	i sila, i slava,
	u vekove vekova.
	
	Amin.
*/

using namespace std;
typedef vector<int> vc;
typedef vector<vector<int>> vvc;
using ll = long long;
using ld = long double;
#define yes cout << "YES\n"
#define no cout << "NO\n"
#define F first
#define S second
#define pb push_back
#define pf push_front
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define int long long

const int mod = 1e9+7;

map<int, int> rwg;
map<int, int> clg;

int pw(int power){
	if(power<0)return 0;
	int ret=1;
	int by=2;
	while(power>0){
		if(power&1){
			ret*=by;
			ret%=mod;
		}
		by<<=1;
		by%=mod;
		power>>=1;
	}
	return ret;
}

void solve(){
	int n, m, k;
	cin >> n >> m >> k;
	if(k==0){
		cout << (pw(n)+pw(m)-2)%mod << '\n';
		return;
	}
	vector<pair<int, int>> a;
	vector<pair<int, int>> b;
	set<int> rw;
	set<int> col;
	for(int i=0; i< k; i++){
		char c;
		int x, y;
		cin >> c >> x >> y;
		rw.insert(x);
		col.insert(y);
		if(c=='+')a.pb({x, y});
		else b.pb({x, y});
	}
	int ans1=n-rw.size();
	int ans2=m-col.size();
	for(pair<int, int> p : a){
		int whr = (p.S%2)? 1:-1;
		if(rwg[p.F]==0)rwg[p.F]=whr;
		else if(rwg[p.F]!=whr)ans1=-1;
	}
	for(pair<int, int> p : b){
		int whr = (p.S%2)? -1:1;
		if(rwg[p.F]==0)rwg[p.F]=whr;
		else if(rwg[p.F]!=whr)ans1=-1;
	}
	for(pair<int, int> p : a){
		int whr = (p.F%2)? 1:-1;
		if(clg[p.S]==0)clg[p.S]=whr;
		else if(clg[p.S]!=whr)ans2=-1;
	}
	for(pair<int, int> p : b){
		int whr = (p.F%2)? -1:1;
		if(clg[p.S]==0)clg[p.S]=whr;
		else if(clg[p.S]!=whr)ans2=-1;
	}
	int chess=0;
	for(pair<int, int> p : a){
		int val=((p.F+p.S)%2)? 1:-1;
		if(chess==0)chess=val;
		if(chess!=val)chess=-2;
	}
	for(pair<int, int> p : b){
		int val = ((p.F+p.S)%2)? -1:1;
		if(chess==0)chess=val;
		if(chess!=val)chess=-2;
	}
	ans1=pw(ans1);
	ans2=pw(ans2);
	if(chess==-2)cout << (ans1+ans2)%mod << '\n';
	else cout << (ans1+ans2-1)%mod << '\n';
}

signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	solve();
	
}

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