Submission #701385

#	Time	Username	Problem	Language	Result	Execution time	Memory
701385		amirhoseinfar1385	Plus Minus (BOI17_plusminus)	C++17	100 / 100	131 ms	14040 KiB

plusminus

#include<bits/stdc++.h>
using namespace std;
long long mod=1e9+7;
long long mypow(long long m,long long y){
	if(y==0){
		return 1;
	}
	long long p=mypow(m,(y>>1));
	p*=p;
	p%=mod;
	if(y&1){
		p*=m;
		p%=mod;
	}
	return p;
}


int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n,m;
	cin>>n>>m;
	int k;
	cin>>k;
	map<int,int>mpr,mpc;
	for(int i=0;i<k;i++){
		int u,v;
		char c;
		cin>>c;
		cin>>u>>v;
		if(c=='+'){
			if(v&1){
				mpr[u]|=1;
			}
			else{
				mpr[u]|=2;
			}
			if(u&1){
				mpc[v]|=1;
			}
			else{
				mpc[v]|=2;
			}
		}
		else{
			if(v&1){
				mpr[u]|=2;
			}
			else{
				mpr[u]|=1;
			}
			if(u&1){
				mpc[v]|=2;
			}
			else{
				mpc[v]|=1;
			}
		}
	}
	vector<pair<int,int>>allr,allc;
	for(auto x:mpr){
		allr.push_back(x);
	}
	for(auto x:mpc){
		allc.push_back(x);
	}
	sort(allr.begin(),allr.end());
	sort(allc.begin(),allc.end());
	int first=1,canfirst=1;
	for(auto x:allr){
		if(x.second==3){
	//		cout<<x.first<<" "<<x.second<<"\n";
			first=0;
		}
	}
	//cout<<first<<"\n";
	for(int i=1;i<(int)allr.size();i++){
		if((allr[i].first-allr[i-1].first)&1){
			if(allr[i].second==allr[i-1].second){
				canfirst=0;
			}
		}
		else{
			if(allr[i].second!=allr[i-1].second){
				canfirst=0;
			}
		}	
	}	
	long long res=0;
	//cout<<first<<"ads \n";
	if(first==1){
	//	cout<<(int)allr.size()<<"\n";
		res+=mypow(2,n-((int)allr.size()));
		if(canfirst==1){
			if(k==0){
				res+=mod-2;
				res%=mod;
			}
			else{
				res+=mod-1;
				res%=mod;
			}
		}
	}
	int second=1;
	for(auto x:allc){
		if(x.second==3){
			second=0;
		}
	}
	if(second==1){
		res+=mypow(2,m-((int)allc.size()));
	}
	res%=mod;
	cout<<res<<"\n";
}

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