Submission #904044

#	Time	Username	Problem	Language	Result	Execution time	Memory
904044		ivaziva	Plus Minus (BOI17_plusminus)	C++14	0 / 100	1 ms	424 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 da1=true,da2=true;
    bool pluss;///1-ako je na neparnim pozicijama,0-ako je na parnim
    long long br=0;
    for (auto&p:map1)
    {
        long long x=p.first;
        long long poz=p.second[0];
        char c=vec[poz].first;
        if (br==0)
        {
            if (c=='+' and x%2==1) pluss=true;
            else if (c=='+' and x%2==0) pluss=false;
            else if (c=='-' and x%2==0) pluss=true;
            else pluss=false;
        }
        else
        {
            if (c=='+' and pluss!=x%2) {da1=false;break;}
            else if (c=='-' and pluss==x%2) {da1=false;break;}
        }
        br++;
    }
    for (auto&p:map2)
    {
        long long x=p.first;
        long long poz=p.second[0];
        char c=vec[poz].first;
        if (c=='+' and pluss!=x%2) {da2=false;break;}
        else if (c=='-' and pluss==x%2) {da2=false;break;}
    }
    if (da1 and da2) return true;
    return false;
}

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 (moguce()) ans--;
    if (k==0) 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;
      |                            ^~
plusminus.cpp: In function 'bool moguce()':
plusminus.cpp:54:24: warning: 'pluss' may be used uninitialized in this function [-Wmaybe-uninitialized]
   54 |         if (c=='+' and pluss!=x%2) {da2=false;break;}
      |                        ^~~~~

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