Submission #372355

#	Time	Username	Problem	Language	Result	Execution time	Memory
372355		dolphingarlic	Plus Minus (BOI17_plusminus)	C++14	100 / 100	290 ms	57324 KiB

plusminus

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

const ll MOD = 1e9 + 7;

ll expo(ll base, int pow) {
    ll ans = 1;
    while (pow) {
        if (pow & 1) ans = (ans * base) % MOD;
        pow >>= 1;
        base = (base * base) % MOD;
    }
    return ans;
}

ll count_ways(int n, int m, map<int, vector<pair<int, char>>> mp) {
    for (auto& i : mp) {
        bool sgn = (i.second[0].first & 1) ^ (i.second[0].second == '+');
        for (pair<int, char> j : i.second) {
            bool needed = (j.first & 1) ^ (j.second == '+');
            if (sgn ^ needed) return 0;
        }
    }
    return expo(2, n - mp.size());
}

int check_both(int n, int m, map<int, vector<pair<int, char>>> mp) {
    if (mp.size() == 0) return 2;
    bool sgn = (mp.begin()->first & 1) ^ (mp.begin()->second[0].first & 1) ^ (mp.begin()->second[0].second == '+');
    for (auto& i : mp) {
        for (pair<int, char> j : i.second) {
            bool needed = (i.first & 1) ^ (j.first & 1) ^ (j.second == '+');
            if (sgn ^ needed) return 0;
        }
    }
    return 1;
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int n, m, k;
    cin >> n >> m >> k;
    map<int, vector<pair<int, char>>> horiz, vert;
    while (k--) {
        char c;
        int x, y;
        cin >> c >> x >> y;
        horiz[x].push_back({y, c});
        vert[y].push_back({x, c});
    }
    cout << (count_ways(n, m, horiz) + count_ways(m, n, vert) - check_both(n, m, horiz)) % MOD;
    return 0;
}

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