Submission #440946

#	Time	Username	Problem	Language	Result	Execution time	Memory
440946		S2speed	Plus Minus (BOI17_plusminus)	C++17	100 / 100	68 ms	7252 KiB

plusminus

#include<bits/stdc++.h>
 
using namespace std;
 
#define all(x) x.begin() , x.end()
#define sze(x) (ll)(x.size())
typedef long long ll;
typedef pair<ll , ll> pll;
typedef pair<pll , bool> pllb;
 
const ll maxn = 2e5 + 16 , md = 1e9 + 7;
 
ll tav(ll n , ll k){
	ll res = 1;
	while(k > 0){
		if(k & 1){
			res *= n; res %= md;
		}
		n *= n; n %= md;
		k >>= 1;
	}
	return res;
}
 
vector<pllb> a , b;
ll ant , bnt;
 
int main(){
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
 
	ll n , m , k;
	cin>>n>>m>>k;
	for(ll i = 0 ; i < k ; i++){
		ll v , u;
		char c;
		cin>>c>>v>>u;
		a.push_back({{v , u} , (c == '+')});
		b.push_back({{u , v} , (c == '+')});
	}
	sort(all(a)); sort(all(b));
	ant = bnt = 1;
	bool ad = false , bd = false;
	for(ll i = 1 ; i < k ; i++){
		if(a[i].first.first != a[i - 1].first.first){
			ant++;
			continue;
		}
		bool c = (a[i].first.second - a[i - 1].first.second) & 1 , d = (a[i].second ^ a[i - 1].second) , h;
		h = c ^ d;
		ad |= h;
	}
	for(ll i = 1 ; i < k ; i++){
		if(b[i].first.first != b[i - 1].first.first){
			bnt++;
			continue;
		}
		bool c = (b[i].first.second - b[i - 1].first.second) & 1 , d = (b[i].second ^ b[i - 1].second) , h;
		h = c ^ d;
		bd |= h;
	}
	if(ad & bd){
		cout<<"0\n";
		return 0;
	}
	ll ans;
	if(!ad & !bd){
		ans = tav(2 , n - ant) + tav(2 , m - bnt) - 1; if(ans >= md) ans -= md;
		if(k == 0){
			ans <<= 1;
			if(ans >= md) ans -= md;
		}
		cout<<ans<<'\n';
		return 0;
	}
	if(bd){
		ans = tav(2 , n - ant);
		cout<<ans<<'\n';
		return 0;
	}
	ans = tav(2 , m - bnt);
	cout<<ans<<'\n';
	return 0;
}

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