Submission #829191

#	Time	Username	Problem	Language	Result	Execution time	Memory
829191		Darren0724	Plus Minus (BOI17_plusminus)	C++17	100 / 100	146 ms	14924 KiB

plusminus

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mod=1e9+7;
map<int,int> fi,row;
int pw(int a,int b){
    int ans=1;
    while(b){
        if(b&1){
            ans=ans*a%mod;
        }
        a=a*a%mod;
        b>>=1;
    }
    return ans;
}
int32_t main(){
    int n,m;cin>>n>>m;
    int q;cin>>q;
    int ans1=0;
    int ans2=0;
    set<int> s;
    for(int i=0;i<q;i++){
        char c;cin>>c;
        int p=(c=='+');
        int a,b;cin>>a>>b;
        if(a%2==0){
            if(!fi.count(b)){
                fi[b]=p^1;
            }
            else if(fi[b]!=(p^1)){
                ans1=-1;
            }
        }
        else{
            if(!fi.count(b)){
                fi[b]=p;
            }
            else if(fi[b]!=p){
                ans1=-1;
            }
        }
        if(!row.count(a)){
            row[a]=(b+p)%2;
        }
        else if(row[a]!=(b+p)%2){ 
            ans2=-1;
        }
        s.insert((a+b+p)%2);
    }
    int m1=m-fi.size();
    int m2=n-row.size();
    if(ans1==-1){
        ans1=0;
    }
    else{
        ans1=pw(2,m1);
    }
    if(ans2==-1){
        ans2=0;
    }
    else{
        ans2=pw(2,m2);
    }
    int ans3=s.size()==1;
    if(q==0){
        ans3=2;
    }
    //cout<<ans1<<' '<<ans2<<' '<<ans3<<endl;
    cout<<(ans1+ans2-ans3+mod)%mod<<endl;

    return 0;
}

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