Submission #699284

#	Time	Username	Problem	Language	Result	Execution time	Memory
699284		_martynas	Plus Minus (BOI17_plusminus)	C++11	100 / 100	248 ms	12916 KiB

plusminus

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using pii = pair<int, int>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vl = vector<ll>;

const int MOD = 1e9+7;

#define F first
#define S second
#define PB push_back
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()

struct Info {
    int sgn, x, y;
};

ll n, m;
int k;

ll mod_pow(ll x, ll y) {
    ll ans = 1;
    while(y) {
        if(y & 1) ans = ans*x%MOD;
        x = x*x%MOD;
        y >>= 1;
    }
    return ans;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> n >> m >> k;
    vector<Info> A(k);
    for(int i = 0; i < k; i++) {
        char c; cin >> c >> A[i].y >> A[i].x;
        A[i].sgn = c == '+';
    }
    // answer = |alternating rows| + |alternating cols| - |alternating both|
    ll ans = 0;
    // rows (group by y check all x)
    map<int, int> total, satisfy;
    bool ok = true;
    for(int i = 0; i < k; i++) {
        total[A[i].y]++;
        satisfy[A[i].y] += (A[i].x % 2 == A[i].sgn);
    }
    for(auto p : total) {
        if(!(p.S == satisfy[p.F] || !satisfy[p.F])) {
            ok = false;
        }
    }
    if(ok) {
        // all other unknown rows can be alternating in 2 different ways
        ans += mod_pow(2, n-total.size());
        ans %= MOD;
    }
    // cols (group by x check all y)
    total.clear(), satisfy.clear();
    ok = true;
    for(int i = 0; i < k; i++) {
        total[A[i].x]++;
        satisfy[A[i].x] += (A[i].y % 2 == A[i].sgn);
    }
    for(auto p : total) {
        if(!(p.S == satisfy[p.F] || !satisfy[p.F])) {
            ok = false;
        }
    }
    if(ok) {
        // all other unknown cols can be alternating in 2 different ways
        ans += mod_pow(2, m-total.size());
        ans %= MOD;
    }
    // subtract double counted variant when both cols and rows are alternating
    // if it's possible to obtain it (only if k == 0 both are possible)
    // (checker pattern)
    if(k == 0) {
        ans = (ans-2+MOD)%MOD;
    }
    else {
        int cnt = 0;
        for(int i = 0; i < k; i++) {
            cnt += (A[i].x % 2 == A[i].y % 2) == A[i].sgn;
        }
        if(cnt == 0 || cnt == k) {
            ans = (ans-1+MOD)%MOD;
        }
    }
    cout << ans << "\n";
    return 0;
}

/*
+ .
. .
2 2 1
+ 1 1

. .
. .
2 2 0


*/

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