Submission #130421

#	Time	Username	Problem	Language	Result	Execution time	Memory
130421		PeppaPig	Plus Minus (BOI17_plusminus)	C++14	100 / 100	165 ms	6556 KiB

plusminus

#include <bits/stdc++.h>

#define long long long
#define pii pair<int, int>
#define x first
#define y second

using namespace std;

const int M = 1e9+7;

long modpow(long a, long b) {
    long ret = 1;
    for( ; b; b >>= 1) {
        if(b & 1) ret = (ret * a) % M;
        a = (a * a) % M;
    }
    return ret;
} 


int n, m, k, valid;
long ans;

void solve(int sz, vector<int> &x, vector<int> &y, vector<int> &val) {
    map<int, int> mp;
    for(int i = 0; i < x.size(); i++) {
        int now = x[i], f = val[i];
        if(y[i] % 2 == 0) f ^= 1;
        if(!mp.count(now)) mp[now] = f;
        else if(mp[now] != f) return;
    }
    ans = (ans + modpow(2, sz - (int)mp.size())) % M;
    int b = -1;
    for(pii p : mp) {
        int now = ((p.x & 1) == p.y);
        if(b == -1) b = now;
        else if(b != now) return;
    }
    ++valid;
}

vector<int> x, y, val;

int main() {
    scanf("%d %d %d", &n, &m, &k);
    if(k == 0) return !printf("%lld\n", (modpow(2, n) + modpow(2, m) - 2 + M) % M);
    for(int i = 1; i <= k; i++) {
        int a, b; char c;
        scanf(" %c %d %d", &c, &a, &b);
        x.emplace_back(a), y.emplace_back(b);
        val.emplace_back(c == '+');
    }
    solve(n, x, y, val), solve(m, y, x, val);
    if(valid == 2) ans = (ans - 1 + M) % M;
    printf("%lld\n", ans);

    return 0;
}

Compilation message (stderr)

plusminus.cpp: In function 'void solve(int, std::vector<int>&, std::vector<int>&, std::vector<int>&)':
plusminus.cpp:27:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < x.size(); i++) {
                    ~~^~~~~~~~~~
plusminus.cpp: In function 'int main()':
plusminus.cpp:46:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d %d", &n, &m, &k);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
plusminus.cpp:50:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf(" %c %d %d", &c, &a, &b);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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