Submission #1115988

#	Time	Username	Problem	Language	Result	Execution time	Memory
1115988		Tozzyyyy	Plus Minus (BOI17_plusminus)	C++14	100 / 100	204 ms	25784 KiB

plusminus

#pragma GCC optimize("Ofast" , "unroll-loops")
#include<bits/stdc++.h>

#define bit(i , j) ((j >> i) & 1)
#define fi first
#define se second
#define all(x) (x).begin() , (x).end()
using namespace std;

const int MAXN = 3e5+100;
const long long inf = 1e9;
const int mod = 1e9+7;

#define int long long
#define pll pair<int , int>
#define MP make_pair

map<int , vector<pll>> Ox , Oy;
int bpow(int a , int b){
	if(b == 0) return 1;
	int res = bpow(a , b/2);
	if(b & 1) return a * res % mod * res % mod;
	else return res * res % mod;
}
int32_t main(){
	//freopen("seq.inp", "r", stdin);
	//freopen("seq.out", "w", stdout);
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	int n , m , k; cin >> n >> m >> k;
	while(k--){
		char c; cin >> c;
		if(c == '+') c = 0;
		if(c == '-') c = 1;
		int x , y; cin >> x >> y;
		Ox[x].push_back({y , c});
		Oy[y].push_back({x , c});
	}

	int ans = 0;
	int res = bpow(2 , n);
	int T = bpow(2 , mod-2);
	for(auto x : Ox){
		vector<vector<int>> v(2 , vector<int>());
		int flag = T;
		for(auto y : x.se){
			if(v[y.fi%2].size() > 0 && v[y.fi%2].back() != y.se) flag = 0;
			v[y.fi%2].push_back(y.se);
		}
		if(v[0].size() > 0 && v[1].size() > 0 && v[0][0] == v[1][0]) flag = 0;
		res = res * flag % mod;
	}
	ans = res;
	res = bpow(2 , m);
	vector<pll> d;
	int count = 1;
	for(auto y : Oy){
		vector<vector<int>> v(2 , vector<int>());
		int flag = T;
		for(auto x : y.se){
			if(v[x.fi%2].size() > 0 && v[x.fi%2].back() != x.se) flag = 0;
			v[x.fi%2].push_back(x.se);
		}
		if(v[0].size() > 0 && v[1].size() > 0 && v[0][0] == v[1][0]) flag = 0;
		if(flag != 0){
			d.push_back({y.fi , y.se[0].se ^ (y.se[0].fi % 2 == 0)});
		}else{
			count = 0; res = 0; break;
		}
		
		res = res * flag % mod;	
	}
	
	if(count == 0){
		cout << (ans + res) % mod << "\n";
		return 0;
	}
	int del = 0;
	if(d.size() == 0) del = 2;
	else{
		vector<vector<int>> v(2 , vector<int>());
		del = 1;
		for(auto x : d){
			if(v[x.fi%2].size() > 0 && v[x.fi%2].back() != x.se) del = 0;
			v[x.fi%2].push_back(x.se);
		}
		if(v[0].size() > 0 && v[1].size() > 0 && v[0][0] == v[1][0]) del = 0;
	}
	res = (res - del + mod) % mod;
	cout << (ans + res) % mod << "\n";

	return 0;
}

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