Submission #719825

#	Time	Username	Problem	Language	Result	Execution time	Memory
719825		Johann	Plus Minus (BOI17_plusminus)	C++14	100 / 100	427 ms	27416 KiB

plusminus

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

#define ll long long
#define vb vector<bool>
#define vi vector<int>
#define vvi vector<vi>
#define F0R(i, n) for (int i = 0; i < (n); ++i)

const int MOD = 1e9+7;

ll conv(ll a, ll b) {
    return 2 * a + b % 2;
}

struct Look {
    map<ll,bool> st;
    void set(ll i) {
        st[i] = true;
    }
    bool get(ll i) {
        if (st.find(i) != st.end()) return true;
        return false;
    }
    ll size() {
        return st.size();
    }
    map<ll,bool>::iterator begin() {
        return st.begin();
    }
    map<ll,bool>::iterator end() {
        return st.end();
    }
};

ll fastExp2(int p) {
    if (p == 0) return 1;
    if (p == 1) return 2;
    ll ans = fastExp2(p / 2);
    ans = (ans * ans) % MOD;
    if (p % 2 == 1) ans *= 2;
    ans %= MOD;
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n,m,k;
    cin >> n >> m >> k;
    // nxm Table: n Reihen, m Spalten
    Look R, RP, RM;
    Look S, SP, SM;

    F0R(i,k) {
        string pm;
        cin >> pm;
        int x,y; // y <= n, x <= M
        cin >> y >> x;
        --x; --y;
        R.set(y);
        S.set(x);
        if (pm[0] == '+') {
            RP.set(conv(y, x));
            SP.set(conv(x, y));
        } else {
            RM.set(conv(y,x));
            SM.set(conv(x,y));
        }
    }


    // Reihen durchgehen
    ll ansR = fastExp2(n - R.size());
    for (auto it = R.begin(); it != R.end(); ++it) {
        ll i = it->first;
        if (   (RP.get(conv(i,0)) && RP.get(conv(i,1)))
            || (RM.get(conv(i,0)) && RM.get(conv(i,1)))
            || (RM.get(conv(i,0)) && RP.get(conv(i,0)))
            || (RM.get(conv(i,1)) && RP.get(conv(i,1)))
        ) {
            ansR *= 0;
        }
    }


    // Spalten durchgehen
    ll ansS = fastExp2(m - S.size());
    for (auto it = S.begin(); it != S.end(); ++it) {
        ll i = it->first;
        if ( (SP.get(conv(i,0)) && SP.get(conv(i,1)))
          || (SM.get(conv(i,0)) && SM.get(conv(i,1)))
          || (SM.get(conv(i,0)) && SP.get(conv(i,0)))
          || (SM.get(conv(i,1)) && SP.get(conv(i,1)))
                ) {
            ansS *= 0;
        }
    }

    ll ans = ansR + ansS;
    // Schachbrett möglich?
    if (ansS > 0 && ansR > 0) {
        --ans;
        if (k == 0) --ans; // hier und nur hier sind sogar beide Schachbretter möglich
    }
    ans = (ans + MOD) % MOD;
    cout << ans << "\n";
}

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