Submission #1088787

#	Time	Username	Problem	Language	Result	Execution time	Memory
1088787		gyg	Plus Minus (BOI17_plusminus)	C++17	100 / 100	118 ms	9724 KiB

plusminus

#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 / 12
• Subtask 2: 42 / 42
• Subtask 3: 46 / 46