Submission #134260

#	Time	Username	Problem	Language	Result	Execution time	Memory
134260		Kastanda	Plus Minus (BOI17_plusminus)	C++11	100 / 100	345 ms	11764 KiB

plusminus

#include<bits/stdc++.h>
using namespace std;
const int N = 100005, Mod = 1e9 + 7;
int n, m, k;
map < int , int > R, C;
inline int Power(int a, int b)
{
    int ret = 1;
    for (; b; b >>= 1, a = 1LL * a * a % Mod)
        if (b & 1) ret = 1LL * ret * a % Mod;
    return (ret);
}
int main()
{
    cin >> n >> m >> k;
    if (!k)
        return !printf("%lld\n", (1LL * Power(2, n) + Power(2, m) - 2LL + Mod) % Mod);
    bool w = 0, f = 0;
    for (int i = 0; i < k; i ++)
    {
        int a, b; char c;
        cin >> c >> a >> b;
        bool tp = (a ^ b ^ (c == '+')) & 1;
        if (!i)
            w = tp;
        else if (w != tp)
            f = 1;
        R[a] |= 1 << ((b ^ (c == '+')) & 1);
        C[b] |= 1 << ((a ^ (c == '+')) & 1);
    }
    int tot = 0;
    bool fr = 0;
    for (auto X : R)
        fr |= (X.second == 3);
    if (!fr)
        tot = Power(2, n - (int)R.size());
    bool fc = 0;
    for (auto X : C)
        fc |= (X.second == 3);
    if (!fc)
        tot = (tot + Power(2, m - (int)C.size())) % Mod;
    if (!f)
        tot = (tot - 1 + Mod) % Mod;
    return !printf("%d\n", tot);
}

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