Submission #1293654

#	Time	Username	Problem	Language	Result	Execution time	Memory
1293654		Hamed_Ghaffari	Plus Minus (BOI17_plusminus)	C++20	100 / 100	91 ms	9828 KiB

plusminus

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

using ll = long long;

#define SZ(x) int(x.size())

const ll MOD = 1e9 + 7;

inline ll power(ll a, ll b) {
    ll res = 1;
    while(b) {
        if(b&1) (res *= a) %= MOD;
        (a *= a) %= MOD;
        b >>= 1;
    }
    return res;
}

int n, m, k, tot;
map<int, bool> rw, cl;
bool badr, badc, badt;

int32_t main() {
    cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
    cin >> n >> m >> k;
    if(k==0) return cout << (power(2, n) + power(2, m) - 2 + MOD)%MOD << '\n', 0;
    tot = -1;
    while(k--) {
        int x, y, z;
        char c;
        cin >> c >> x >> y;
        z = c=='+';
        if(rw.find(x)==rw.end()) rw[x] = (y&1)^z;
        else if(((y&1)^z)!=rw[x]) badr = 1;
        if(cl.find(y)==cl.end()) cl[y] = (x&1)^z;
        else if(((x&1)^z)!=cl[y]) badc = 1;
        if(tot==-1) tot = (x&1)^(y&1)^z;
        else if(((x&1)^(y&1)^z)!=tot) badt = 1;
    }
    ll ans = 0;
    if(!badr) (ans += power(2, n-SZ(rw))) %= MOD;
    if(!badc) (ans += power(2, m-SZ(cl))) %= MOD;
    if(!badt) (ans += MOD-1) %= MOD;
    cout << ans << '\n';
    return 0;
}

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