제출 #1194228

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1194228		_rain_	Plus Minus (BOI17_plusminus)	C++20	100 / 100	149 ms	55008 KiB

plusminus

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

map<int,vector<pair<int,char>>>ngang,doc;
int numrow,numcol,k;

const int MOD=(int)1e9+7;
	int add(int a,int b){
		return a+b>=MOD?a+b-MOD:a+b;
	}
	int mul(int a,int b){
		return (LL)a*b%MOD;
	}
	int sub(int a,int b){
		return a-b<0?a-b+MOD:a-b;
	}
	int power(int a,int b){
		int res=1;
		for(;b;b>>=1,a=mul(a,a)){
			if (b&1) res=mul(res,a);
		}
		return res;
	}
	
int count_ways(int n,map<int,vector<pair<int,char>>>cnt){
	for(auto&i:cnt){
		bool sgn=(i.second[0].first%2) ^ (i.second[0].second=='+');
		for(auto&j:i.second){
			bool other_sgn=(j.first%2) ^ (j.second=='+');
			if (sgn^other_sgn) return 0;
		}
	}
	return power(2,n-cnt.size());
}

int both(int n,map<int,vector<pair<int,char>>>cnt){
	if (cnt.size()==0) return 2;
	bool f_sgn=(cnt.begin()->first%2) ^ (cnt.begin()->second[0].second=='+') ^ (cnt.begin()->second[0].first%2);
	for(auto&i:cnt){
		for(auto&j:i.second){
			bool other_sgn=(j.first%2) ^ (j.second=='+') ^ (i.first%2);
			if (f_sgn^other_sgn) return 0;
		}
	
	}
	return 1;
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0) ; cout.tie(0);
//	freopen("main.inp","r",stdin);
	
	cin>>numrow>>numcol>>k;
	for(int i=1;i<=k;++i){
		char sgn; cin>>sgn;
		int x,y; cin>>x>>y;
		ngang[x].push_back({y,sgn});
		doc[y].push_back({x,sgn});
	}
	cout<<sub(add(count_ways(numrow,ngang),count_ways(numcol,doc)),both(numrow,ngang));
}

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