oj.uz

답안 #699284

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
699284 2023-02-16T12:33:48 Z _martynas Plus Minus (BOI17_plusminus) C++11
100 / 100
 248 ms 12916 KB 
#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using pii = pair<int, int>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vl = vector<ll>;

const int MOD = 1e9+7;

#define F first
#define S second
#define PB push_back
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()

struct Info {
    int sgn, x, y;
};

ll n, m;
int k;

ll mod_pow(ll x, ll y) {
    ll ans = 1;
    while(y) {
        if(y & 1) ans = ans*x%MOD;
        x = x*x%MOD;
        y >>= 1;
    }
    return ans;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> n >> m >> k;
    vector<Info> A(k);
    for(int i = 0; i < k; i++) {
        char c; cin >> c >> A[i].y >> A[i].x;
        A[i].sgn = c == '+';
    }
    // answer = |alternating rows| + |alternating cols| - |alternating both|
    ll ans = 0;
    // rows (group by y check all x)
    map<int, int> total, satisfy;
    bool ok = true;
    for(int i = 0; i < k; i++) {
        total[A[i].y]++;
        satisfy[A[i].y] += (A[i].x % 2 == A[i].sgn);
    }
    for(auto p : total) {
        if(!(p.S == satisfy[p.F] || !satisfy[p.F])) {
            ok = false;
        }
    }
    if(ok) {
        // all other unknown rows can be alternating in 2 different ways
        ans += mod_pow(2, n-total.size());
        ans %= MOD;
    }
    // cols (group by x check all y)
    total.clear(), satisfy.clear();
    ok = true;
    for(int i = 0; i < k; i++) {
        total[A[i].x]++;
        satisfy[A[i].x] += (A[i].y % 2 == A[i].sgn);
    }
    for(auto p : total) {
        if(!(p.S == satisfy[p.F] || !satisfy[p.F])) {
            ok = false;
        }
    }
    if(ok) {
        // all other unknown cols can be alternating in 2 different ways
        ans += mod_pow(2, m-total.size());
        ans %= MOD;
    }
    // subtract double counted variant when both cols and rows are alternating
    // if it's possible to obtain it (only if k == 0 both are possible)
    // (checker pattern)
    if(k == 0) {
        ans = (ans-2+MOD)%MOD;
    }
    else {
        int cnt = 0;
        for(int i = 0; i < k; i++) {
            cnt += (A[i].x % 2 == A[i].y % 2) == A[i].sgn;
        }
        if(cnt == 0 || cnt == k) {
            ans = (ans-1+MOD)%MOD;
        }
    }
    cout << ans << "\n";
    return 0;
}

/*
+ .
. .
2 2 1
+ 1 1

. .
. .
2 2 0


*/

Subtask #1
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 320 KB Output is correct
6 Correct 1 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 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct

Subtask #2
42.0 / 42.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 320 KB Output is correct
6 Correct 1 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 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 49 ms 2516 KB Output is correct
17 Correct 46 ms 2496 KB Output is correct
18 Correct 38 ms 2508 KB Output is correct
19 Correct 38 ms 2508 KB Output is correct
20 Correct 38 ms 2472 KB Output is correct

Subtask #3
46.0 / 46.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 320 KB Output is correct
6 Correct 1 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 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 49 ms 2516 KB Output is correct
17 Correct 46 ms 2496 KB Output is correct
18 Correct 38 ms 2508 KB Output is correct
19 Correct 38 ms 2508 KB Output is correct
20 Correct 38 ms 2472 KB Output is correct
21 Correct 162 ms 8388 KB Output is correct
22 Correct 0 ms 212 KB Output is correct
23 Correct 132 ms 8376 KB Output is correct
24 Correct 150 ms 8400 KB Output is correct
25 Correct 134 ms 8444 KB Output is correct
26 Correct 176 ms 10896 KB Output is correct
27 Correct 202 ms 10920 KB Output is correct
28 Correct 185 ms 10892 KB Output is correct
29 Correct 164 ms 10800 KB Output is correct
30 Correct 248 ms 12916 KB Output is correct