Submission #130414

#	Time	Username	Problem	Language	Result	Execution time	Memory
130414		PeppaPig	Plus Minus (BOI17_plusminus)	C++14	0 / 100	2 ms	256 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;
int v_x, v_y;
long ans;

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

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, a, b, c; i <= k; i++) {
        scanf(" %c %d %d", &c, &a, &b);
        c = c == '+' ? 1 : -1;
        x.emplace_back(a), y.emplace_back(b);
        val.emplace_back(c);
    }
    solve(n, x, val), solve(m, y, val);
    if(v_x == 2) ans = (ans - 1 + M) % M;
    if(v_y == 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>&)':
plusminus.cpp:28:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < v.size(); i++) {
                    ~~^~~~~~~~~~
plusminus.cpp: In function 'int main()':
plusminus.cpp:49:38: warning: format '%c' expects argument of type 'char*', but argument 2 has type 'int*' [-Wformat=]
         scanf(" %c %d %d", &c, &a, &b);
                            ~~        ^
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:49: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: 0 / 12
• Subtask 2: 0 / 42
• Subtask 3: 0 / 46