Submission #896132

#	Time	Username	Problem	Language	Result	Execution time	Memory
896132		AlphaMale06	Plus Minus (BOI17_plusminus)	C++14	100 / 100	165 ms	25948 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;

ll exp(ll x, ll n, ll m) {
	if(n<0)return 0;
	x %= m;
	ll res = 1;
	while (n > 0) {
		if (n % 2 == 1) {  
			res = res * x % m;
		}
		x = x * x % m;
		n /= 2; 
	}
	return res;
}


void solve(){
	int n, m, k;
	cin >> n >> m >> k;
	if(k==0){
		cout << ((exp(2, n, mod)+exp(2, m, mod)-2)%mod+mod)%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=exp(2, ans1, mod);
	ans2=exp(2, ans2, mod);
	if(chess==-2)cout << (ans1+ans2)%mod << '\n';
	else cout << ((ans1+ans2-1)%mod+mod)%mod << '\n';
}

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

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