Submission #706225

#	Time	Username	Problem	Language	Result	Execution time	Memory
706225		ToroTN	Plus Minus (BOI17_plusminus)	C++14	100 / 100	342 ms	36728 KiB

plusminus

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
ll r,c,n,x,y,pls,mns,ans,cnt,MOD=1e9+7,type,bruh=0;
char op[5];
map<ll,ll> plus_x,minus_x,plus_y,minus_y;
set<ll> s_x,s_y,s,s2;
ll power_2(ll u)
{
    ll pow_2[35];
    pow_2[0]=2;
    for(int i=1;i<=30;i++)
    {
        pow_2[i]=pow_2[i-1]*pow_2[i-1];
        pow_2[i]%=MOD;
    }
    vector<ll> v;
    while(1)
    {
        if(u<=1)
        {
            v.pb(u);
            break;
        }
        v.pb(u%2);
        u/=2;
    }
    ll afk=1;
    for(int i=0;i<v.size();i++)
    {
        if(v[i]==1)
        {
            afk*=pow_2[i];
            afk%=MOD;
        }
    }
    return afk;
}
int main()
{
    scanf("%lld%lld%lld",&r,&c,&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%s%lld%lld",op,&x,&y);
        s_x.insert(x);
        s_y.insert(y);
        if(op[0]=='+')
        {
            plus_x[x]|=(1<<(y%2));
            plus_y[y]|=(1<<(x%2));
        }else
        {
            minus_x[x]|=(1<<(y%2));
            minus_y[y]|=(1<<(x%2));
        }
    }
    ans=0;
    cnt=1;
    for(auto it=s_x.begin();it!=s_x.end();it++)
    {
        pls=plus_x[(*it)],mns=minus_x[(*it)];
        if(pls==0&&mns==0)
        {
            cnt*=2;
            cnt%=MOD;
        }else if(pls==mns)
        {
            cnt=0;
            bruh^=1;
            break;
        }else if(pls!=3&&mns!=3)
        {
            cnt*=1;
            cnt%=MOD;
            if(pls==2||mns==1)
            {
                type=0;
            }else
            {
                type=1;
            }
            s2.insert(((*it)+type)%2);
        }else
        {
            cnt=0;
            bruh^=1;
            break;
        }
    }
    cnt*=power_2(r-s_x.size());
    cnt%=MOD;
    ans+=cnt;
    ans%=MOD;
    cnt=1;
    for(auto it=s_y.begin();it!=s_y.end();it++)
    {
        pls=plus_y[(*it)],mns=minus_y[(*it)];
        if(pls==0&&mns==0)
        {
            cnt*=2;
            cnt%=MOD;
        }else if(pls==mns)
        {
            cnt=0;
            bruh^=2;
            break;
        }else if(pls!=3&&mns!=3)
        {
            cnt*=1;
            cnt%=MOD;
            if(pls==2||mns==1)
            {
                type=0;
            }else
            {
                type=1;
            }
            s.insert(((*it)+type)%2);
        }else
        {
            cnt=0;
            bruh^=2;
            break;
        }
    }
    cnt*=power_2(c-s_y.size());
    cnt%=MOD;
    ans+=cnt;
    ans%=MOD;
    if(n==0)
    {
        ans-=2;
        ans+=MOD;
        ans%=MOD;
    }else if(bruh==3)
    {
        ans=0;
    }else
    {
        if(s.size()==1&&s2.size()==1)
        {
            ans-=1;
            ans+=MOD;
            ans%=MOD;
        }
    }
    printf("%lld\n",ans);
}

Compilation message (stderr)

plusminus.cpp: In function 'long long int power_2(long long int)':
plusminus.cpp:30:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |     for(int i=0;i<v.size();i++)
      |                 ~^~~~~~~~~
plusminus.cpp: In function 'int main()':
plusminus.cpp:42:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   42 |     scanf("%lld%lld%lld",&r,&c,&n);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
plusminus.cpp:45:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   45 |         scanf("%s%lld%lld",op,&x,&y);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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