Submission #148106

#	Time	Username	Problem	Language	Result	Execution time	Memory
148106		WhipppedCream	Plus Minus (BOI17_plusminus)	C++17	100 / 100	164 ms	13080 KiB

plusminus

#include <bits/stdc++.h>
#define ii pair<int, int>
#define X first
#define Y second
#define pb push_back
#define mp make_pair
#define vi vector<int>
#define vii vector< pair<int, int> >
typedef long long ll;
using namespace std;
struct node
{
    int typ, x, y;
    node(){}
    node(int a, int b, int c)
    {
        typ = a;
        x = b;
        y = c;
    }
    bool operator < (node other) const
    {
        if(y != other.y) return y< other.y;
        return x< other.x;
    }
};
const int md = 1e9 + 7;
int add(int a, int b)
{
    return (a+b)%md;
}
int sub(int a, int b)
{
    return (a-b+md)%md;
}
int mul(int a, int b)
{
    return (1LL*a*b)%md;
}
int power(int a, int b)
{
    if(b == 0) return 1;
    int x = power(a, b/2);
    int y = mul(x, x);
    if(b%2) y = mul(y, a);
    return y;
}
vector<node> foo;
map<int, int> longfix;
int main()
{
    int n, m, k;
    scanf("%d %d %d", &n, &m, &k);
    for(int i = 0; i< k; i++)
    {
        char t; int x, y;
        scanf(" %c %d %d", &t, &x, &y);
        foo.pb(node(t, x, y));
    }
    sort(foo.begin(), foo.end());
    int ans = 0;
    //Check for case 1: all are alternating
    //Condition: No connected component in each column.
    bool ok = 1;
    map<int, int> mag;
    if(foo.empty())
    {
        ans = add(ans, power(2, m));
        ans = add(ans, power(2, n));
        ans = sub(ans, 2);
        printf("%d\n", ans);
        return 0;
    }
    else
    {
        for(int i = 0; i< (int) foo.size(); i++)
        {
            int k = (foo[i].typ == '+')?1:-1;
            int x = foo[i].x, y = foo[i].y;
            if(x%2 == 0) k = -k;
            if(mag.find(y) == mag.end()) mag[y] = k;
            else if(mag[y] != k)
            {
                ok = 0;
                break;
            }
        }
        int fix = mag.size();
        assert(fix<= m);
        if(ok) ans = add(ans, power(2, m-fix));
    }
    int ok2 = 1;
    for(int i = 0; i< (int) foo.size(); i++)
    {
        int k = (foo[i].typ == '+')?1:-1;
        int x = foo[i].x; int y = foo[i].y;
        if(y%2 == 0) k = -k;
        if(longfix.find(x) == longfix.end()) longfix[x] = k;
        else if(longfix[x] != k)
        {
            ok2 = 0;
            break;
        }
    }
    int fix = longfix.size();
    assert(fix<= n);
    if(ok2) ans = add(ans, power(2, n-fix));
    if(ok && ok2)
    {
        bool good1 = 1, good2 = 1;
        for(auto x : longfix)
        {
            if((x.first%2 == 1 && x.second == -1) || (x.first%2 == 0 && x.second == 1)) good1 = 0;
            if((x.first%2 == 1 && x.second == 1) || (x.first%2 == 0 && x.second == -1)) good2 = 0;
        }
        for(auto x : mag)
        {
            if((x.first%2 == 1 && x.second == -1) || (x.first%2 == 0 && x.second == 1)) good1 = 0;
            if((x.first%2 == 1 && x.second == 1) || (x.first%2 == 0 && x.second == -1)) good2 = 0;
        }
        if(good1) ans = sub(ans, 1);
        if(good2) ans = sub(ans, 1);
    }
    printf("%d\n", ans);
    return 0;
}

Compilation message (stderr)

plusminus.cpp: In function 'int main()':
plusminus.cpp:53:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d %d", &n, &m, &k);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
plusminus.cpp:57:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf(" %c %d %d", &t, &x, &y);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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