Submission #1091181

#	Time	Username	Problem	Language	Result	Execution time	Memory
1091181		Math4Life2020	Plus Minus (BOI17_plusminus)	C++17	100 / 100	101 ms	14932 KiB

plusminus

#include <bits/stdc++.h>
using namespace std;
using ll = long long; 
using pii = pair<ll,ll>;
const ll p = 1e9+7;
const ll i2 = 5e8+4;

ll e2(ll x) {
    x %= (p-1);
    if (x==0) {
        return 1;
    } else if (x==1) {
        return 2;
    } else if (x%2==0) {
        ll y = e2(x/2);
        return (y*y)%p;
    } else {
        ll y = e2(x/2);
        return (2*y*y)%p;
    }
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);
    /*freopen("io.txt","r",stdin);
    freopen("out.txt","w",stdout);*/
    ll N,M,K; cin >> N >> M >> K;
    if (K==0) {
        cout << (e2(N)+e2(M)-2)%p; exit(0);
    }
    ll pt = -1; ll ans = 0;
    map<ll,ll> px,py;
    for (ll k=0;k<K;k++) {
        string s; ll x,y; cin >> s >> x >> y;
        x--; y--;
        ll vpt,vpx,vpy;
        if (s=="+") {
            vpt = (x+y)%2;
            vpx = x%2;
            vpy = y%2;
        } else {
            vpt = (x+y+1)%2;
            vpx = (x+1)%2;
            vpy = (y+1)%2;
        }
        if (pt==-1) {
            pt=vpt;
        } else if (pt != vpt) {
            pt=-2;
        }
        if (py.find(y)==py.end()) {
            py[y]=vpx;
        } else if (py[y]!=vpx) {
            py[y]=-1;
        }
        if (px.find(x)==px.end()) {
            px[x]=vpy;
        } else if (px[x]!=vpy) {
            px[x]=-1;
        }
    }
    if (pt==-1) {
        ans += (p-2);
    } else if (pt==0 || pt==1) {
        ans += (p-1);
    }
    ll ax = e2(N); ll ay = e2(M);
    for (pii p0: px) {
        if (p0.second==-1) {
            ax = 0;
        } else {
            ax = (ax*i2)%p;
        }
    }
    for (pii p0: py) {
        if (p0.second==-1) {
            ay = 0;
        } else {
            ay = (ay*i2)%p;
        }
    }
    ans = (ans+ax+ay)%p;
    cout << ans;
}

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