oj.uz

답안 #731631

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
731631 2023-04-27T17:04:36 Z adrilen Plus Minus (BOI17_plusminus) C++17
0 / 100
 1 ms 320 KB 
#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 };
    tri last = { -1, -1, 0 };


    for (int f = 0; f < 2; f++)
    {
        sort(v.begin(), v.end());
    
        int lines = m;
        // cout << "\n";
        for (tri t : v)
        {
            // cout << t.x << " " << t.y << " " << lines << "\n";
            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);
            // cout << output << "\n";
        }

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

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 320 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 0 ms 320 KB Output is correct
10 Incorrect 1 ms 212 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #2
0 / 42.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 320 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 0 ms 320 KB Output is correct
10 Incorrect 1 ms 212 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #3
0 / 46.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 320 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 0 ms 320 KB Output is correct
10 Incorrect 1 ms 212 KB Output isn't correct
11 Halted 0 ms 0 KB -