제출 #1066586

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1066586		thinknoexit	Plus Minus (BOI17_plusminus)	C++17	100 / 100	88 ms	9808 KiB

plusminus

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const ll MOD = 1e9 + 7;
map<int, int> r, c;
ll mop(ll a, ll p) {
    ll ans = 1;
    for (;p != 0ll;p >>= 1ll, a = a * a % MOD) {
        if (p & 1ll) ans = ans * a % MOD;
    }
    return ans;
}
int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int n, m, k;
    cin >> n >> m >> k;
    if (n == 1) {
        cout << mop(2, m - k) << '\n';
        return 0;
    }
    if (m == 1) {
        cout << mop(2, n - k) << '\n';
        return 0;
    }
    int cr = n, cc = m;
    int in0 = 1, in1 = 1;
    while (k--) {
        char C;
        int x, y;
        cin >> C >> x >> y;
        int st = C == '+';
        int rst = (y & 1) ^ st, cst = (x & 1) ^ st;
        if ((x & 1) ^ (y & 1) ^ st) in0 = 0;
        else in1 = 0;
        // row
        if (cr != -1) {
            if (!r.count(x)) r[x] = rst, cr--;
            else if (r[x] != rst) cr = -1;
        }
        // col
        if (cc != -1) {
            if (!c.count(y)) c[y] = cst, cc--;
            else if (c[y] != cst) cc = -1;
        }
    }
    // handle interception cases
    if (cr == -1 && cc == -1) {
        cout << 0 << '\n';
        return 0;
    }
    ll ans = 0;
    if (cr != -1) ans = (ans + mop(2, cr)) % MOD;
    if (cc != -1) ans = (ans + mop(2, cc)) % MOD;
    cout << (ans - in0 - in1 + MOD) % MOD << '\n';
    return 0;
}

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