제출 #731634

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
731634		adrilen	Plus Minus (BOI17_plusminus)	C++17	100 / 100	44 ms	3528 KiB

plusminus

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
typedef pair<int, int> pii;
constexpr ll mod = 1e9 + 7;


ll binary_exp(ll base, ll power)
{
    if (power == 0) return 1;

    ll output = 1;
    ll inc = 2;

    for (int i = 0; i < 32; i++)
    {
        if (power & (1 << i)) {

            output *= inc;
            output %= mod;
        }
        inc *= inc;
        inc %= mod;
    }

    // cout << base << " " << power << " " << output <<"\n";

    return output;
}

struct tri{
    int x, y;
    bool b;

    void s()
    {
        swap(x, y);
    }

    bool operator<(const tri &t) const {
        if (x == t.x) return y < t.y;
        return x < t.x;
    }
} ;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    ll n, m, k;
    cin >> n >> m >> k;
    
    ll output = 0;
    if (k == 0)
    {
        output = binary_exp(2, n) + binary_exp(2, m) - 2;
        output %= mod;
        cout << output << "\n";
        return 0;
    }

    vector <tri> v(k);

    char c;
    int a, b;
    for (int i = 0; i < k; i++)
    {
        cin >> c >> a >> b;
        v[i] = tri{b, a, (c == '+')};
    }

    bool direction[2] = { 0 };


    for (int f = 0; f < 2; f++)
    {
        sort(v.begin(), v.end());
    
        int lines = m;
        tri last = { -1, -1, 0 };

        for (tri t : v)
        {
            if (last.x == -1) {
                lines--;
            }
            else if (t.x == last.x)
            {
                if (t.b == last.b)
                {
                    if (abs(t.y - last.y) & 1) {direction[f] = 1; break;}
                    else continue;
                } else {
                    if (abs(t.y - last.y) & 1) continue;
                    else {direction[f] = 1; break;}
                }
            } else {
                lines--;
            }

            last = t;
        }

        if (!direction[f]) {
            output += binary_exp(2, lines);
        }

        for (tri &t : v) t.s();
        swap(m, n);
    }


    int l = -1;
    bool removed = false;
    if (!direction[0] && !direction[1]) {
        removed = true;
        for (tri t : v)
        {
            if (l == -1)
            {
                l = (t.x + t.y + t.b) & 1; 
            } 
            else {
                if (((t.x + t.y + t.b) & 1) == l) continue;
                else removed = false; 
            }
        }
    }
    output -= removed;
    output %= mod;

    cout << output << "\n";
    // cerr << direction[0] << " " << direction[1] << "\n";
}

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