Submission #904050

#	Time	Username	Problem	Language	Result	Execution time	Memory
904050		ivaziva	Plus Minus (BOI17_plusminus)	C++14	54 / 100	192 ms	45256 KiB

plusminus

#include <bits/stdc++.h>

using namespace std;

#define MOD 1000000007

long long n,m,k;
vector<pair<char,pair<long long,long long>>> vec;
map<long long,vector<long long>> map1;
map<long long,vector<long long>> map2;

long long stepen(long long a,long long b)
{
    if (a>=MOD) a%=MOD;
    long long res=1;
    while (b>0)
    {
        if (b&1) res=res*a;if (res>=MOD) res%=MOD;
        a=a*a;if (a>=MOD) a%=MOD;
        b>>=1;
    }
    return res;
}

bool moguce()
{
    bool pluss;
    long long x,y;
    char c;
    x=vec[1].second.first;
    y=vec[1].second.second;
    c=vec[1].first;
    if (c=='+' and (x+y)%2==0) pluss=false;
    else if (c=='+' and (x+y)%2==1) pluss=true;
    else if (c=='-' and (x+y)%2==1) pluss=false;
    else pluss=true;
    bool da=true;
    for (long long i=2;i<=n;i++)
    {
        x=vec[i].second.first;y=vec[i].second.second;
        c=vec[i].first;
        if (c=='+' and (x+y)%2!=pluss) {da=false;break;}
        else if (c=='-' and (x+y)%2==pluss) {da=false;break;}
    }
    return da;
}

int main()
{
    cin>>n>>m>>k;
    for (long long i=0;i<k;i++)
    {
        char c; cin>>c;
        long long x,y; cin>>x>>y;
        vec.push_back({c,{x,y}});
        map1[x].push_back(i);map2[y].push_back(i);
    }
    bool da1=true,da2=true;
    for (auto&p:map1)
    {
        long long s=p.second.size();
        bool pluss;///1-ako je neparan,0-ako je paran
        long long poz=p.second[0];
        char c=vec[poz].first;
        long long y=vec[poz].second.second;
        if (c=='+' and y%2==0) pluss=false;
        else if (c=='+' and y%2==1) pluss=true;
        else if (c=='-' and y%2==0) pluss=true;
        else pluss=false;
        for (long long i=1;i<s;i++)
        {
            poz=p.second[i];c=vec[poz].first;y=vec[poz].second.second;
            if (c=='+' and y%2!=pluss) {da1=false;break;}
            else if (c=='-' and y%2==pluss) {da1=false;break;}
        }
        if (!da1) break;
    }
    for (auto&p:map2)
    {
        long long s=p.second.size();
        bool pluss;///1-ako je neparan,0-ako je paran
        long long poz=p.second[0];
        char c=vec[poz].first;
        long long y=vec[poz].second.first;
        if (c=='+' and y%2==0) pluss=false;
        else if (c=='+' and y%2==1) pluss=true;
        else if (c=='-' and y%2==0) pluss=true;
        else pluss=false;
        for (long long i=1;i<s;i++)
        {
            poz=p.second[i];c=vec[poz].first;y=vec[poz].second.first;
            if (c=='+' and y%2!=pluss) {da2=false;break;}
            if (c=='-' and y%2==pluss) {da2=false;break;}
        }
        if (!da2) break;
    }
    if (da1==false and da2==false) {cout<<0<<endl;return 0;}
    else if (da1==false)
    {
        long long ans2=stepen(2,m-map2.size());
        cout<<ans2<<endl;
        return 0;
    }
    else if (da2==false)
    {
        long long ans1=stepen(2,n-map1.size());
        cout<<ans1<<endl;
        return 0;
    }
    long long ans1=stepen(2,n-map1.size());
    long long ans2=stepen(2,m-map2.size());
    long long ans=ans1+ans2;
    if (ans>=MOD) ans%=MOD;
    if (k==0) ans-=2;
    else if (moguce()) ans--;
    if (ans<0) ans+=MOD;
    cout<<ans<<endl;
    return 0;
}

Compilation message (stderr)

plusminus.cpp: In function 'long long int stepen(long long int, long long int)':
plusminus.cpp:18:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   18 |         if (b&1) res=res*a;if (res>=MOD) res%=MOD;
      |         ^~
plusminus.cpp:18:28: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   18 |         if (b&1) res=res*a;if (res>=MOD) res%=MOD;
      |                            ^~

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