Submission #557846

#	Time	Username	Problem	Language	Result	Execution time	Memory
557846		fatemetmhr	Plus Minus (BOI17_plusminus)	C++17	100 / 100	216 ms	26704 KiB

plusminus

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

#define pb     push_back
#define all(x) x.begin(), x.end()
#define fi     first
#define se     second

const int maxn5 = 2e3 + 10;
const int mod   = 1e9 + 7;

map <ll, vector <pair<ll, int>>> avsatr, avstoon;
vector <pair<pair<ll, ll>, int>> have;

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

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

    int n, m, k; cin >> n >> m >> k;

    if(k == 0){
        return cout << (pw(2, n) + pw(2, m) + mod - 2) % mod << endl, 0;
    }

    for(int i = 0; i < k; i++){
        int x, y;
        char ty; cin >> ty >> x >> y;
        x--; y--;
        avsatr[x].pb({y, ty == '+' ? 0 : 1});
        avstoon[y].pb({x, ty == '+' ? 0 : 1});
        have.pb({{x, y}, ty == '+' ? 0 : 1});
    }

    ll ans = 0;
    bool ok = true;
    for(auto it = avstoon.begin(); it != avstoon.end(); it++){
        int v = (it -> fi);
        bool re1 = true, re2 = true;
        for(auto [u, z] : (it -> se)){
            re1 &= ((v + u) % 2 == z);
            re2 &= ((v + u) % 2 != z);
        }
        ok &= (re1 || re2);
    }
    if(ok)
        ans = pw(2, m - avstoon.size());

    //cout << "ok " << ans << endl;

    ok = true;
    for(auto it = avsatr.begin(); it != avsatr.end(); it++){
        int v = (it -> fi);
        bool re1 = true, re2 = true;
        for(auto [u, z] : (it -> se)){
            re1 &= ((v + u) % 2 == z);
            re2 &= ((v + u) % 2 != z);
            //cout << "ok " << v << ' '<< u << ' ' << z << ' ' << re1 << ' ' << re2 << endl;
        }
        ok &= (re1 || re2);
    }
    //cout << "then " << ok << ' ' << avsatr.size() << endl;
    if(ok)
        ans = (ans + pw(2, n - avsatr.size())) % mod;

    //cout << ans << endl;

    bool re1 = true, re2 = true;
    for(auto [p, z] : have){
        int x = p.fi, y = p.se;
        re1 &= ((x + y) % 2 == z);
        re2 &= ((x + y) % 2 != z);
    }
    if(re1 || re2)
        ans = (ans + mod - 1) % mod;
    cout << ans << endl;
}

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