Submission #1275769

#	Time	Username	Problem	Language	Result	Execution time	Memory
1275769		SinaPourkashani	Plus Minus (BOI17_plusminus)	C++20	100 / 100	131 ms	24512 KiB

plusminus

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef vector<ll> vll;
typedef vector <pair<ll, ll>> vp;
typedef pair<ll, ll> pll;
typedef map <ll, ll> mll;
typedef set <ll> sll;
#define pb push_back
#define ff first
#define ss second
#define str to_string
#define all(x) (x).begin(), (x).end()
#define print(x) for (auto i : x) cout << i << ' '; cout << '\n';
#define FastIO ios_base::sync_with_stdio(false); cin.tie(NULL);

const ll maxn = 3e5+5;
const ll mod = 1e9+7;
const ll inf = 1e18;

ll pw(ll a, ll b, ll M = mod) {ll ans = 1; for (; b; a = ((a * a) % M), b >>= 1) if (b & 1) ans = (ans * a) % M; return ans;}

ll n, m, k;
map <ll, vector <pair <char, ll>>> vx, vy;

int main() {
    FastIO

    cin >> n >> m >> k;

    vector <pair <char, pll>> pos;
    for (ll i = 1; i <= k; i++) {
        ll x, y;
        char c;
        cin >> c >> x >> y;
        vx[x].pb({c, y});
        vy[y].pb({c, x});
        pos.pb({c, {x, y}});
    }

    ll ans = 0;
    bool flag = true;

    for (auto &[i, vct] : vx) {
        sll st1, st2;
        for (auto &[c, j] : vct) {
            if (c == '-') {
                st1.insert(j&1);
                if (st2.find((j&1)) != st2.end()) {
                    flag = false;
                }
            } else {
                st2.insert(j&1);
                if (st1.find((j&1)) != st1.end()) {
                    flag = false;
                }
            }
        }

        if (st1.size() == 2) flag = false;
        if (st2.size() == 2) flag = false;
    }

    if (flag) {
        ans += pw(2, n-vx.size());
    }

    flag = true;
    for (auto &[i, vct] : vy) {
        sll st1, st2;
        for (auto &[c, j] : vct) {
            if (c == '-') {
                st1.insert(j&1);
                if (st2.find((j&1)) != st2.end()) {
                    flag = false;
                }
            } else {
                st2.insert(j&1);
                if (st1.find((j&1)) != st1.end()) {
                    flag = false;
                }
            }
        }

        if (st1.size() == 2) flag = false;
        if (st2.size() == 2) flag = false;
    }

    if (flag) {
        ans += pw(2, m-vy.size());
    }

    flag = true;
    for (auto &[c, p] : pos) {
        if (c == '-') {
            if (p.ff%2 != p.ss%2) flag = false;
        } else {
            if (p.ff%2 == p.ss%2) flag = false;
        }
    }

    if (flag) ans--;

    flag = true;
    for (auto &[c, p] : pos) {
        if (c == '+') {
            if (p.ff%2 != p.ss%2) flag = false;
        } else {
            if (p.ff%2 == p.ss%2) flag = false;
        }
    }

    if (flag) ans--;

    cout << (ans + mod) % mod << '\n';  

    return 0;
}

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