제출 #670929

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
670929		Makarooni	Plus Minus (BOI17_plusminus)	C++14	100 / 100	240 ms	36852 KiB

plusminus

/* IN THE NAME OF GOD */
/* |\/| /-\ |\| | |\/| /-\ */

#include "bits/stdc++.h"
using namespace std;

#define sz(x) (int)x.size()
#define endl '\n'
#define pb push_back
#define all(x) x.begin(), x.end()
#define F first
#define S second
#define mr make_pair
//#define int long long
#define pii pair<int, int>
typedef long double ld;
typedef long long ll;

mt19937 rng (chrono::high_resolution_clock::now().time_since_epoch().count());

const int N = 2e5 + 10;
const ll MOD = 1e9 + 7;
const int inf = 1e9;
const ll INF = 2e18;

vector<int> h[N][2], w[N][2];
vector<int> vx, vy;
int Q[N][3];

int pw(int a, int b){
	if(b == 0)
		return 1;
	int p = pw(a, b / 2);
	p = (1LL * p * p) % MOD;
	if(b % 2)
		p = (1LL * p * a) % MOD;
	return p;
}

int fx(int x){
	return lower_bound(all(vx), x) - vx.begin();
}

int fy(int y){
	return lower_bound(all(vy), y) - vy.begin();
}

int32_t main(){
	ios_base:: sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int n, m, q;
	cin >> n >> m >> q;
	char s;
	int x, y;
	set<int> X, Y;
	for(int i = 1; i <= q; i++){
		cin >> s >> x >> y;
		vx.pb(x);
		vy.pb(y);
		Q[i][0] = (s == '+');
		Q[i][1] = x;
		Q[i][2] = y;
	}
	sort(all(vx));
	sort(all(vy));
	vx.resize(unique(all(vx)) - vx.begin());
	vy.resize(unique(all(vy)) - vy.begin());
	int t;
	for(int i = 1; i <= q; i++){
		t = Q[i][0];
		x = Q[i][1];
		y = Q[i][2];
		h[fx(x)][y % 2].pb(t);
		w[fy(y)][x % 2].pb(t);
		X.insert(x);
		Y.insert(y);
	}
	bool f = 1;
	for(int i = 0; i <= 100000; i++){
		for(int j = 1; j < sz(h[i][0]); j++){
			if(h[i][0][j] != h[i][0][j - 1]){
				f = 0;
				break;
			}
		}
		if(!f)
			break;
		for(int j = 1; j < sz(h[i][1]); j++){
			if(h[i][1][j] != h[i][1][j - 1]){
				f = 0;
				break;
			}
		}
		if(!f)
			break;
		if(sz(h[i][0]) >= 1 && sz(h[i][1]) >= 1){
			if(h[i][0][0] == h[i][1][0]){
				f = 0;
				break;
			}
		}
	}
	bool f2 = 1;
	for(int i = 0; i <= 100000; i++){
		for(int j = 1; j < sz(w[i][0]); j++){
			if(w[i][0][j] != w[i][0][j - 1]){
				f2 = 0;
				break;
			}
		}
		if(!f2)
			break;
		for(int j = 1; j < sz(w[i][1]); j++){
			if(w[i][1][j] != w[i][1][j - 1]){
				f2 = 0;
				break;
			}
		}
		if(!f2)
			break;
		if(sz(w[i][0]) >= 1 && sz(w[i][1]) >= 1){
			if(w[i][0][0] == w[i][1][0]){
				f2 = 0;
				break;
			}
		}
	}
	//cout << n << " " << sz(X) << endl;
	ll ans = 0;
	if(f)
		ans = pw(2, n - sz(X));
	if(f2)
		ans += pw(2, m - sz(Y));
	ans %= MOD;
	if(f && f2)
		ans--;
	if(q == 0)
		ans--;
	if(ans < 0)
		ans += MOD;
	cout << ans;
}

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