제출 #1275843

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1275843		ehsan1011000	Plus Minus (BOI17_plusminus)	C++20	100 / 100	210 ms	19044 KiB

plusminus

#include <bits/stdc++.h>
#include <iomanip>
 
using namespace std;
 
# define pb push_back
# define pf push_front
# define ff first
# define ss second
# define ll long long
# define lc id * 2
# define rc lc | 1
//# define int long long
# define mid (r + l) / 2
//# define mp make_pair
typedef long double ld;
#define kill(x)  cout << x << '\n', exit(0)
typedef pair<int, char> pic;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef priority_queue<pll, vector<pll>, greater<pll>> pq;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const ll maxn = 1e5 + 10, maxm = 4e5 + 10, sq = 1300, LOG = 30, mod = 1e9 + 7;
const ll inf = 1e17;
int n, m, k;
set<pii> st0, st1, ts0, ts1;
set<int> sts[2];

inline ll Pow(ll a, ll b, ll mod){
    ll ans = 1ll;
    while(b){
        if(b & 1) ans = ans * a % mod;
        b >>= 1, a = a * a % mod;
    }
    return ans;
}

int main() {
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	cin >> n >> m >> k;
	bool check = 1, check2 = 1;
	set<int> cols, rws;
	for(int i = 1; i <= k; i ++){
		char c;
		int v, u;
		cin >> c >> v >> u;
		cols.insert(u);
		rws.insert(v);
		bool b = 0;
		if(c == '-') b = 1;
		if(b) sts[v % 2].insert(u % 2);
		else sts[v % 2].insert(! (u % 2));
		if(v % 2){
			st0.insert({u, b});
			if(st1.find({u, b}) != st1.end() || st0.find({u, ! b}) != st0.end()) check = 0;
		}
		else{
			st1.insert({u, b});
			if(st0.find({u, b}) != st0.end() || st1.find({u, ! b}) != st1.end()) check = 0;
		}
		if(u % 2){
			ts0.insert({v, b});
			if(ts1.find({v, b}) != ts1.end() || ts0.find({v, ! b}) != ts0.end()) check2 = 0;
		}
		else{
			ts1.insert({v, b});
			if(ts0.find({v, b}) != ts0.end() || ts1.find({v, ! b}) != ts1.find({v, ! b})) check2 = 0;
		}
	}
	ll ans = 0;
	if(check) ans = Pow(2, m - cols.size(), mod);
	if(check2){
		ans = (ans + Pow(2, n - rws.size(), mod)) % mod;
		if((sts[0].find(1) != sts[0].end() && sts[1].find(1) != sts[1].end()) || (sts[0].find(0) != sts[0].end() && sts[1].find(0) != sts[1].end())) {}
		else if(k > 0) ans = (ans - 1 + mod) % mod;
		else ans = (ans - 2 + mod) % mod;
	}
	cout << ans << '\n';
    return 0; 
}

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