Submission #1066578

#	Time	Username	Problem	Language	Result	Execution time	Memory
1066578		thinknoexit	Plus Minus (BOI17_plusminus)	C++17	0 / 100	0 ms	344 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) {
        int all = m;
        while (k--) {
            char C;
            int x, y;
            cin >> C >> x >> y;
            int st = C == '+';
            if (all != -1) {
                if (!c.count(y)) c[y] = st, all--;
                else if (c[y] != st) all = -1;
            }
        }
        if (all == -1) cout << 0 << '\n';
        else cout << mop(2, all) << '\n';
        return 0;
    }
    if (m == 1) {
        int all = n;
        while (k--) {
            char C;
            int x, y;
            cin >> C >> x >> y;
            int st = C == '+';
            if (all != -1) {
                if (!c.count(x)) c[x] = st, all--;
                else if (c[x] != st) all = -1;
            }
        }
        if (all == -1) cout << 0 << '\n';
        else cout << mop(2, all) << '\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 (cst == rst) 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 = 1;
    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: 0 / 12
• Subtask 2: 0 / 42
• Subtask 3: 0 / 46