Submission #480312

#	Time	Username	Problem	Language	Result	Execution time	Memory
480312		Alexandruabcde	Plus Minus (BOI17_plusminus)	C++14	100 / 100	56 ms	3600 KiB

plusminus

#include <bits/stdc++.h>

using namespace std;

constexpr int MOD = 1e9 + 7;
constexpr int NMAX = 1e5 + 5;

struct Point {
    int x;
    int y;
    char ch;
};

Point A[NMAX];

int N, M, K;

bool cmp_1 (Point a, Point b) {
    return a.x < b.x;
}

bool cmp_2 (Point a, Point b) {
    return a.y < b.y;
}

int Value (char ch) {
    if (ch == '+') return 1;

    return 0;
}

int LogPut (int a, int b) {
    if (b == 0) return 1;
    if (b == 1) return a;

    int val = LogPut(a, b/2);
    if (b % 2 == 0) return (1LL * val * val) % MOD;
    else return (1LL * val * val * a) % MOD;
}

void Read () {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> N >> M >> K;

    for (int i = 1; i <= K; ++ i )
        cin >> A[i].ch >> A[i].x >> A[i].y;
}

int ParalelLines () {
    sort(A+1, A+K+1, cmp_1);
    int ans = 1;
    int Total_Lines = N;

    for (int i = 1; i <= K; ++ i ) {
        int j = i;
        int mat[2][2];
        memset(mat, 0, sizeof(mat));
        -- Total_Lines;

        while (j <= K && A[j].x == A[i].x) ++ j;
        -- j;

        for (int k = i; k <= j; ++ k )
            mat[A[k].y%2][Value(A[k].ch)] ++;

        if ((mat[0][0] != 0 && mat[1][0] != 0) || (mat[0][1] != 0 && mat[1][1] != 0) || (mat[0][0] != 0 && mat[0][1] != 0) || (mat[1][0] != 0 && mat[1][1] != 0)) {
            ans = 0;
            break;
        }

        i = j;
    }

    return ans * LogPut(2, Total_Lines);
}

int ParalelColumns () {
    sort(A+1, A+K+1, cmp_2);
    int ans = 1;
    int Total_Columns = M;

    for (int i = 1; i <= K; ++ i ) {
        int j = i;
        int mat[2][2];
        memset(mat, 0, sizeof(mat));
        -- Total_Columns;

        while (j <= K && A[j].y == A[i].y) ++ j;
        -- j;

        for (int k = i; k <= j; ++ k )
            mat[A[k].x%2][Value(A[k].ch)] ++;

        if ((mat[0][0] != 0 && mat[1][0] != 0) || (mat[0][1] != 0 && mat[1][1] != 0) || (mat[0][0] != 0 && mat[0][1] != 0) || (mat[1][0] != 0 && mat[1][1] != 0)) {
            ans = 0;
            break;
        }

        i = j;
    }

    return ans * LogPut(2, Total_Columns);
}

int ParalelLinesandColumns () {
    int mat[2][2];
    memset(mat, 0, sizeof(mat));
    for (int i = 1; i <= K; ++ i )
        mat[(A[i].x + A[i].y)%2][Value(A[i].ch)]++;

    if (K == 0) return 2;

    if ((mat[0][0] >= 0 && mat[1][1] >= 0 && mat[1][0] == 0 && mat[0][1] == 0) || (mat[0][1] >= 0 && mat[1][0] >= 0 && mat[0][0] == 0 && mat[1][1] == 0))
        return 1;

    return 0;
}

int main () {
    Read();
    int ans = (1LL * ParalelLines() + 1LL * ParalelColumns() - 1LL * ParalelLinesandColumns() + MOD) % MOD;

    cout << ans << '\n';
    return 0;
}

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