Submission #481357

#	Time	Username	Problem	Language	Result	Execution time	Memory
481357		DJeniUp	Plus Minus (BOI17_plusminus)	C++17	100 / 100	366 ms	29688 KiB

plusminus

//#pragma GCC Optimize("O3")
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll>pairll;
typedef pair<ll,pairll>pairlll;
typedef pair<pairll,pairll>pairllll;
typedef long double ld;
typedef pair<ll,string>pairls;

#define INF 1000000000000007
#define MOD 1000000007
#define pb push_back
#define fr first
#define sc second
#define endl '\n'

ll n,m,k,X,Y;

struct D{
    ll a,b,h;
}d[100007];

map<ll,ll>f1,g1,f2,g2;

ll S(ll x,ll y){
    ll res=1;
    while(y>0){
        if(y%2==1){
            res*=x;
            res%=MOD;
        }
        x*=x;
        x%=MOD;
        y/=2;
    }
    return res;
}

int main() {
    
    cin>>n>>m>>k;
    ll N=n;
    ll M=m;
    if(k==0){
        cout<<(S(2,n)+S(2,m)-2)%MOD;
        return 0;
    }
    for(int i=1;i<=k;i++){
        char c;
        cin>>c>>d[i].a>>d[i].b;
        if(c=='+')d[i].h=1;
        else d[i].h=0;
    }
    for(int i=1;i<=k;i++){
        if(f1[d[i].a]==0){
            f1[d[i].a]=1;
            g1[d[i].a]=(d[i].b+d[i].h)%2;
            n--;
        }else{
            if(g1[d[i].a]!=(d[i].b+d[i].h)%2){
                X=1;
            }
        }

        if(f2[d[i].b]==0){
            f2[d[i].b]=1;
            g2[d[i].b]=(d[i].a+d[i].h)%2;
            m--;
        }else{
            if(g2[d[i].b]!=(d[i].a+d[i].h)%2){
                Y=1;
            }
        }
    }
    if(N==1){
        cout<<S(2,m)<<endl;
    }else if(M==1){
        cout<<S(2,n)<<endl;
    }else if(X==1 && Y==1){
        cout<<0<<endl;
    }else if(X==0 && Y==1){
        cout<<S(2,n)<<endl;
    }else if(X==1 && Y==0){
        cout<<S(2,m)<<endl;
    }else{
        cout<<(S(2,n)+S(2,m)-1)%MOD<<endl;
    }

}

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