제출 #1275876

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1275876		mhn_neek	Plus Minus (BOI17_plusminus)	C++20	100 / 100	397 ms	45056 KiB

plusminus

// IN THE NAME OF GOD
#include<bits/stdc++.h>
using namespace std;
typedef long long int lli;
typedef pair<lli,lli> pii;
typedef vector<lli> ve;
typedef vector<pii> vp;
const lli N = 5e5 + 100;
const lli INF = 1e18;
const lli mod = 1e9 + 7;
lli power(lli a,lli b){
	if(b == 0)return 1LL;
	lli res = power(a,b/2);
	res = (res*res)%mod;
	if(b%2 == 1)res = (res*a)%mod;
	return res;
}
#define debug(x) cerr<<(#x)<<" "<<x<<endl
#define PB push_back
#define MP make_pair
#define fi first
#define se second
#define FOR(x,y) for(lli x = 0; x < y; x ++)
#define FORS(x,y) for(lli x = 1; x <= y; x ++)
#define all(x) x.begin(),x.end()
#define lb lower_bound
#define ub upper_bound
lli n,m,k;
set<lli> useR,useC;
map<lli,vp> row,lac[2];

map<pii,lli> typ;

map<lli,lli> cel[2];
set<lli> det[2];
lli ANS = 0;
lli sum[2];
int main(){
	ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n>>m>>k;
	vector<pair<lli,pii>> E;
	FORS(i,k){
		char ch;
		cin>>ch;
		lli no = (ch == '+' ? 1 : 0);
		lli a,b;
		cin>>a>>b;
		sum[(no+(a%2)+(b%2))%2  ]++;
		E.PB(MP(no,MP(a,b)));
		typ[MP(a,b)]=no;
		useR.insert(a);
		useC.insert(b);
		row[a].PB(MP(b,no));
	}
	bool ok = 1;
	for(auto a : useR){
		for(auto [b,no] : row[a]){
			if(det[a%2].find(b)!=det[a%2].end()){
				if(cel[a%2][b]!=no){
					ok = 0;
				}
				continue;
			}
			else{
				cel[a%2][b] = no;
				det[a%2].insert(b);
			}
		}
	}
	set<lli> S;
	for(auto i : det[0]){
		if(det[1].find(i)!=det[1].end()){
			if(cel[0][i] == cel[1][i]){
				ok=0;
			}
		}
		S.insert(i);
	}
	for(auto i : det[1])S.insert(i);
	lli ans = power(2,m-(lli)S.size());
	ANS += ans*ok;
	ok = 1;
	row.clear();
	lac[0].clear();
	lac[1].clear();
	det[0].clear();
	det[1].clear();
	cel[0].clear();
	cel[1].clear();
	
	FORS(i,k){
		lli no = E[i-1].fi;
		lli a=E[i-1].se.fi,b=E[i-1].se.se;
		row[b].PB(MP(a,no));
	}
	for(auto b : useC){
		for(auto [a,no] : row[b]){
			if(det[b%2].find(a)!=det[b%2].end()){
				if(cel[b%2][a]!=no){
					ok = 0;
				}
				continue;
			}
			else{
				cel[b%2][a] = no;
				det[b%2].insert(a);
			}
		}
	}
	S.clear();
	for(auto i : det[0]){
		if(det[1].find(i)!=det[1].end()){
			if(cel[0][i] == cel[1][i]){
				ok = 0;
			}
		}
		S.insert(i);
	}
	for(auto i : det[1])S.insert(i);
	ans = power(2,n-(lli)S.size());
	ANS += ans*ok;
	ANS -= (sum[0]==0);
	ANS -= (sum[1]==0);
	ANS += mod;
	ANS %= mod;
	cout<<ANS<<endl;




}

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