Submission #484656

#	Time	Username	Problem	Language	Result	Execution time	Memory
484656		SirCovidThe19th	Plus Minus (BOI17_plusminus)	C++17	100 / 100	342 ms	44684 KiB

plusminus

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

#define FOR(i, x, y) for (int i = x; i < y; i++)
#define ll long long
#define pii pair<int, int>
#define f first
#define s second

const int md = 1e9 + 7;

int n, m, k; ll ans; map<int, set<pii>> R, C;

ll binPow(ll a, ll p){
    ll ret = 1;
    for (;p; p /= 2, a = a * a % md) if (p & 1) ret = ret * a % md;
    return ret;
}
void solve(int tot, map<int, set<pii>> mp){
    for (auto &S : mp){
        pii prv = {};
        for (auto cur : S.s){
            if (prv.f and ((cur.f - prv.f) & 1) != (cur.s ^ prv.s)) return;
            prv = cur;
        }
    }
    ans += binPow(2, tot - mp.size());
}
void overCnt(map<int, set<pii>> mp){
    bool case1 = 1, case2 = 1;
    for (auto &S : mp) for (auto cur : S.s){
        int req = (S.f & 1) ^ (cur.f & 1);
        case1 &= (cur.s == req);
        case2 &= (cur.s != req);
    }
    ans -= (case1 + case2);
}

int main(){
    cin >> n >> m >> k;
    FOR(i, 0, k){
        char c; int x, y; cin >> c >> x >> y;
        R[x].insert({y, c == '+'});
        C[y].insert({x, c == '+'});
    }
    solve(n, R); solve(m, C); overCnt(R);
    cout<<(ans + md) % md<<endl;
}

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