Submission #405173

#	Time	Username	Problem	Language	Result	Execution time	Memory
405173		ritul_kr_singh	Plus Minus (BOI17_plusminus)	C++17	100 / 100	124 ms	17360 KiB

plusminus

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define sp << ' ' <<
#define nl << '\n'

const int MOD = 1e9+7, INF = 1e18;

int p(int i){
	int res = 1, mul = 2;
	while(i){
		if(i & 1) res = (res * mul) % MOD;
		mul = (mul * mul) % MOD;
		i /= 2LL;
	}
	return res;
}

signed main(){
	cin.tie(0)->sync_with_stdio(0);
	int n, m, k; cin >> n >> m >> k;
	vector<int> xs, ys;
	array<int, 3> e[k];

	int w = - 1, ok = 1;

	for(auto &i : e){
		char j;
		cin >> j >> i[0] >> i[1];
		i[2] = j == '+';
		xs.push_back(i[0]);
		ys.push_back(i[1]);
		if(w < 0) w = (i[0] + i[1] + i[2]) % 2;
		else if(w != (i[0] + i[1] + i[2]) % 2) ok = 0;
	}

	sort(xs.begin(), xs.end());
	sort(ys.begin(), ys.end());

	vector<array<int, 2>> a[2][k];

	for(auto &i : e){
		a[0][lower_bound(xs.begin(), xs.end(), i[0])-xs.begin()].push_back({i[1], i[2]});
		a[1][lower_bound(ys.begin(), ys.end(), i[1])-ys.begin()].push_back({i[0], i[2]});
	}

	int cnt = 0, ans = 0, add = 0;

	for(int _=0; _<2; ++_){
		cnt = _ ? m : n;
		for(auto &i : a[_]){
			if(i.empty()) continue;
			--cnt;
			int z = (i[0][0]+i[0][1]) % 2;
			for(auto &j : i){
				if(z != (j[0]+j[1]) % 2) cnt = -INF;
			}
		}
		if(cnt >=0) ans += p(cnt), ++add;
	}
	if(k == 0) ans = (ans - 2 + MOD) % MOD;
	else if(add == 2) ans = (ans - ok + MOD) % MOD;
	cout << ans;
}

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