Submission #550442

#	Time	Username	Problem	Language	Result	Execution time	Memory
550442		Jarif_Rahman	Plus Minus (BOI17_plusminus)	C++17	100 / 100	120 ms	13332 KiB

plusminus

#include <bits/stdc++.h>
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;

const ll md = 1e9+7;

ll pw(ll x, ll p){
    if(p == 0) return 1;
    if(p%2 == 0) return pw((x*x)%md, p/2);
    return (pw(x, p-1)*x)%md;
}

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

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

    vector<tuple<str, ll, ll>> points(k);

    for(auto &[c, x, y]: points) cin >> c >> x >> y;

    ll ans = 0;

    {
        bool ok = 1;
        ll cnt = n;
        map<ll, bool> mp;

        for(int i = 0; i < k; i++){
            auto [c, x, y] = points[i];
            if(mp.find(x) == mp.end()){
                mp[x] = ((c=="+")!=(y%2==1));
                cnt--;
            }
            else{
                if(mp[x] != ((c=="+")!=(y%2==1))) ok = 0;
            }
        }

        if(ok) ans+=pw(2, cnt), ans%=md;
    }
    {
        bool ok = 1;
        ll cnt = m;
        map<ll, bool> mp;

        for(int i = 0; i < k; i++){
            auto [c, x, y] = points[i];
            if(mp.find(y) == mp.end()){
                mp[y] = ((c=="+")!=(x%2==1));
                cnt--;
            }
            else{
                if(mp[y] != ((c=="+")!=(x%2==1))) ok = 0;
            }
        }

        if(ok) ans+=pw(2, cnt), ans%=md;
    }
    {
        bool ok1 = 1, ok2 = 1;
        for(int i = 0; i < k; i++){
            auto [c, x, y] = points[i];
            if((x+y)%2 == (c=="+")) ok1 = 0;
            else ok2 = 0;
        }

        if(ok1) ans--;
        if(ok2) ans--;
        ans%=md;
        if(ans < 0) ans+=md;
    }

    cout << ans << "\n";
}

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