oj.uz

Submission #1088787

# Submission time Handle Problem Language Result Execution time Memory
1088787 2024-09-15T05:31:36 Z gyg Plus Minus (BOI17_plusminus) C++17
100 / 100
 118 ms 9724 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define arr array
#define vct vector
#define hmap unordered_map
#define pii pair<int, int>
const int MX_N = 1e5 + 5, MD = 1e9 + 7;

int r, c, n;
arr<int, MX_N> vl;
arr<pii, MX_N> ps;

int md(int x) { return (x + MD) % MD; }
int expn(int x, int y) {
    if (y == 0) return 1;
    int hlf = expn(x, y / 2);
    int ans = md(hlf * hlf);
    if (y % 2 == 1) ans = md(ans * x);
    return ans;
}
int flp(int x) { return ((x % 2 == 0) ? 1 : -1); }
int slv(int rw, int cl, int x, int y, int z) { // {1, 1}, {rw, 1}, {1, cl}
    return flp(rw + cl + 1) * x + flp(cl + 1) * y + flp(rw + 1) * z;
}
int slv_rw(int rw, int cl, int x, int y, int z) { // {rw, cl}, {1, 1}, {1, cl}
    return flp(cl + 1) * (x - flp(rw + cl + 1) * y - flp(rw + 1) * z);
}
int slv_cl(int rw, int cl, int x, int y, int z) { // {rw, cl}, {1, 1}, {rw, 1}
    return flp(rw + 1) * (x - flp(rw + cl + 1) * y - flp(cl + 1) * z);
}
int chck(int x) {
    for (int i = 1; i <= n; i++) {
        int rw = ps[i].first, cl = ps[i].second;
        if (rw == 1 && cl == 1) {
            if (vl[i] != x) return false;
        } else if (rw == 1) {
            if (vl[i] != flp(cl + 1) * x) return false;
        } else if (cl == 1) {
            if (vl[i] != flp(rw + 1) * x) return false;
        } else if (vl[i] != slv(rw, cl, x, flp(rw + 1) * x, flp(cl + 1) * x)) return false;
    }
    return true;
}

int cmp() {
    int ans = 0;
    for (int x : {-1, 1}) {
        for (bool is_rw : {true, false}) {
            bool hlt = false;
            for (int i = 1; i <= n; i++) {
                int rw = ps[i].first, cl = ps[i].second;
                if (is_rw && cl == 1 && vl[i] != flp(rw + 1) * x) hlt = true;
                if (!is_rw && rw == 1 && vl[i] != flp(cl + 1) * x) hlt = true;
            }
            if (hlt) continue;

            hmap<int, int> fxd = {{1, x}};
            for (int i = 1; i <= n; i++) {
                int rw = ps[i].first, cl = ps[i].second;
                if (is_rw && rw == 1) fxd.insert({cl, vl[i]});
                if (!is_rw && cl == 1) fxd.insert({rw, vl[i]});
            }
            
            for (int i = 1; i <= n; i++) {
                int rw = ps[i].first, cl = ps[i].second;
                if (min(rw, cl) == 1) continue;
                if (is_rw && fxd.count(cl) && fxd[cl] != slv_cl(rw, cl, vl[i], x, flp(rw + 1) * x)) hlt = true;
                if (!is_rw && fxd.count(rw) && fxd[rw] != slv_rw(rw, cl, vl[i], x, flp(cl + 1) * x)) hlt = true;
                if (is_rw) fxd.insert({cl, slv_cl(rw, cl, vl[i], x, flp(rw + 1) * x)});
                if (!is_rw) fxd.insert({rw, slv_rw(rw, cl, vl[i], x, flp(cl + 1) * x)});
            }
            if (hlt) continue;
            int nw_ans = (is_rw) ? expn(2, c - fxd.size()) : expn(2, r - fxd.size());
            ans = md(ans + nw_ans);
        }
        ans -= chck(x);
    }
    return ans;
}

signed main() {
    // freopen("pls.in", "r", stdin);
    cin >> r >> c >> n;
    for (int i = 1; i <= n; i++) {
        char x; cin >> x >> ps[i].first >> ps[i].second;
        vl[i] = (x == '+') ? 1 : -1;
    }

    int ans = cmp();
    cout << ans << endl;
}

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct

Subtask #2
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 30 ms 3668 KB Output is correct
17 Correct 29 ms 3664 KB Output is correct
18 Correct 29 ms 3544 KB Output is correct
19 Correct 34 ms 3572 KB Output is correct
20 Correct 35 ms 3648 KB Output is correct

Subtask #3
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 30 ms 3668 KB Output is correct
17 Correct 29 ms 3664 KB Output is correct
18 Correct 29 ms 3544 KB Output is correct
19 Correct 34 ms 3572 KB Output is correct
20 Correct 35 ms 3648 KB Output is correct
21 Correct 61 ms 6652 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 52 ms 6576 KB Output is correct
24 Correct 53 ms 6516 KB Output is correct
25 Correct 70 ms 6520 KB Output is correct
26 Correct 82 ms 8088 KB Output is correct
27 Correct 83 ms 8092 KB Output is correct
28 Correct 81 ms 8200 KB Output is correct
29 Correct 90 ms 8344 KB Output is correct
30 Correct 118 ms 9724 KB Output is correct