oj.uz

Submission #904050

# Submission time Handle Problem Language Result Execution time Memory
904050 2024-01-11T18:45:49 Z ivaziva Plus Minus (BOI17_plusminus) C++14
54 / 100
 192 ms 45256 KB 
#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

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.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 432 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct

Subtask #2
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 432 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 604 KB Output is correct
15 Correct 1 ms 604 KB Output is correct
16 Correct 67 ms 6408 KB Output is correct
17 Correct 76 ms 6576 KB Output is correct
18 Correct 55 ms 7540 KB Output is correct
19 Correct 56 ms 6276 KB Output is correct
20 Correct 56 ms 7452 KB Output is correct

Subtask #3
0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 432 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 604 KB Output is correct
15 Correct 1 ms 604 KB Output is correct
16 Correct 67 ms 6408 KB Output is correct
17 Correct 76 ms 6576 KB Output is correct
18 Correct 55 ms 7540 KB Output is correct
19 Correct 56 ms 6276 KB Output is correct
20 Correct 56 ms 7452 KB Output is correct
21 Correct 190 ms 17656 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 169 ms 17676 KB Output is correct
24 Correct 155 ms 17344 KB Output is correct
25 Correct 144 ms 17412 KB Output is correct
26 Correct 180 ms 22672 KB Output is correct
27 Correct 189 ms 22808 KB Output is correct
28 Correct 182 ms 22276 KB Output is correct
29 Runtime error 192 ms 45256 KB Execution killed with signal 11
30 Halted 0 ms 0 KB -