Submission #631139

#	Time	Username	Problem	Language	Result	Execution time	Memory
631139		CDuong	Plus Minus (BOI17_plusminus)	C++14	100 / 100	144 ms	9832 KiB

plusminus

#include <bits/stdc++.h>
#define int long long
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define endl '\n'
#define pii pair<int, int>
using namespace std;
const int mxN = 1e5 + 5;
const int mod = 1e9 + 7;
struct point{
    char c; int x, y;
    point(){}
    point(char c1, int x1, int y1){
        c = c1; x = x1; y = y1;
    }
};
int n, m, k, ans;
vector<point> v;
int binpow(int x, int y){
    int res = 1;
    while(y != 0){
        if(y % 2 == 1) res = (res * x) % mod;
        x = (x * x) % mod;
        y /= 2;
    }
    return res;
}
void check1(){
    int cnt = n;
    bool flag = true;
    map<int, int> m1;
    for(int i = 0; i < k; ++i){
        point tmp = v[i];
        int tmp1 = ((tmp.c == '+') != (tmp.y % 2 == 1));
        if(m1.find(tmp.x) == m1.end()){
            m1[tmp.x] = tmp1;
            cnt--;
        }
        else{
            if(m1[tmp.x] != tmp1) flag = false;
        }
    }
    if(flag) ans = (ans + binpow(2, cnt)) % mod;
}
void check2(){
    int cnt = m;
    bool flag = true;
    map<int, int> m1;
    for(int i = 0; i < k; ++i){
        point tmp = v[i];
        int tmp1 = ((tmp.c == '+') != (tmp.x % 2 == 1));
        if(m1.find(tmp.y) == m1.end()){
            m1[tmp.y] = tmp1;
            cnt--;
        }
        else{
            if(m1[tmp.y] != tmp1) flag = false;
        }
    }
    if(flag) ans = (ans + binpow(2, cnt)) % mod;
}
void check3(){
    bool flag, flag1; flag = flag1 = true;
    for(int i = 0; i < k; ++i){
        point tmp = v[i];
        if((tmp.x + tmp.y) % 2 == (tmp.c == '+')) flag = false;
        else flag1 = false;
    }
    if(flag) ans--;
    if(flag1) ans--;
    cout << ans << endl;
}
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    //freopen("Bai3.inp", "r", stdin);
    //freopen("Bai3.out", "w", stdout);
    cin >> n >> m >> k;
    for(int i = 1; i <= k; ++i){
        char c; int x, y;
        cin >> c >> x >> y;
        point tmp(c, x, y);
        v.pb(tmp);
    }
    check1(); check2(); check3();
}

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