# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
796403 | 2023-07-28T11:13:04 Z | MadokaMagicaFan | Plus Minus (BOI17_plusminus) | C++14 | 99 ms | 9548 KB |
#include "bits/stdc++.h" using namespace std; using ll = long long; ll md = 1e9+7; ll pw(int x) { ll a = 1; ll c = 2; while (x) { if (x&1) a = (a * c) % md; c = (c * c) % md; x >>= 1; } return a; } int32_t main(int32_t argc, char *argv[]) { if (argc > 1) freopen(argv[1], "r", stdin); int n, m, k; char c; set<int> cx, cy; cin >> n >> m >> k; if (k == 0) { cout << (pw(m) + pw(n) - 2ll) << endl; return 0; } vector<array<int, 3>> pn(k); for (int i = 0; i < k; ++i) { cin >> c >> pn[i][1] >> pn[i][2]; --pn[i][1], --pn[i][2]; cy.insert(pn[i][1]); cx.insert(pn[i][2]); pn[i][0] = (c == '+') ? 0 : 1; } int hx, hy; hx = hy = 0; vector<array<int, 3>> sm(k); for (int i = 0; i < k; ++i) { sm[i][0] = pn[i][1]; sm[i][1] = pn[i][2]; sm[i][2] = pn[i][0]; } sort(sm.begin(), sm.end()); for (int i = 1; i < k; ++i) { if (sm[i][0] != sm[i-1][0]) continue; if (((sm[i][1] ^ sm[i][2]) ^ (sm[i-1][1] ^ sm[i-1][2])) & 1) { hx = 1; break; } } for (int i = 0; i < k; ++i) { sm[i][0] = pn[i][2]; sm[i][1] = pn[i][1]; sm[i][2] = pn[i][0]; } sort(sm.begin(), sm.end()); for (int i = 1; i < k; ++i) { if (sm[i][0] != sm[i-1][0]) continue; if (((sm[i][1] ^ sm[i][2]) ^ (sm[i-1][1] ^ sm[i-1][2])) & 1) { hy = 1; break; } } assert(n > 1); assert(m > 1); //TODO: test for not possible if (hx && hy) { cout << 0 << endl; return 0; } if (hx == 1) { // PRINTX: cout << pw(m - cx.size()) << endl; return 0; } if (hy == 1) { // PRINTY: cout << pw(n - cy.size()) << endl; return 0; } ll ans = (pw(m - cx.size()) + pw(n - cy.size()) - 1ll) % md; for (int i = 1; i < k; ++i) { if (((pn[i][0] ^ pn[i][1] ^ pn[i][2]) ^ (pn[0][0] ^ pn[0][1] ^ pn[0][2])) & 1) { ans = (ans + 1ll) % md; break; } } cout << ans << endl; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 212 KB | Output is correct |
2 | Correct | 1 ms | 304 KB | Output is correct |
3 | Correct | 1 ms | 212 KB | Output is correct |
4 | Correct | 0 ms | 212 KB | Output is correct |
5 | Correct | 1 ms | 212 KB | Output is correct |
6 | Correct | 0 ms | 212 KB | Output is correct |
7 | Correct | 1 ms | 212 KB | Output is correct |
8 | Correct | 0 ms | 212 KB | Output is correct |
9 | Correct | 0 ms | 212 KB | Output is correct |
10 | Correct | 1 ms | 212 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 212 KB | Output is correct |
2 | Correct | 1 ms | 304 KB | Output is correct |
3 | Correct | 1 ms | 212 KB | Output is correct |
4 | Correct | 0 ms | 212 KB | Output is correct |
5 | Correct | 1 ms | 212 KB | Output is correct |
6 | Correct | 0 ms | 212 KB | Output is correct |
7 | Correct | 1 ms | 212 KB | Output is correct |
8 | Correct | 0 ms | 212 KB | Output is correct |
9 | Correct | 0 ms | 212 KB | Output is correct |
10 | Correct | 1 ms | 212 KB | Output is correct |
11 | Correct | 1 ms | 340 KB | Output is correct |
12 | Correct | 1 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 | 312 KB | Output is correct |
16 | Correct | 63 ms | 3588 KB | Output is correct |
17 | Correct | 64 ms | 3596 KB | Output is correct |
18 | Correct | 63 ms | 3684 KB | Output is correct |
19 | Correct | 67 ms | 3660 KB | Output is correct |
20 | Correct | 78 ms | 3640 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 212 KB | Output is correct |
2 | Correct | 1 ms | 304 KB | Output is correct |
3 | Correct | 1 ms | 212 KB | Output is correct |
4 | Correct | 0 ms | 212 KB | Output is correct |
5 | Correct | 1 ms | 212 KB | Output is correct |
6 | Correct | 0 ms | 212 KB | Output is correct |
7 | Correct | 1 ms | 212 KB | Output is correct |
8 | Correct | 0 ms | 212 KB | Output is correct |
9 | Correct | 0 ms | 212 KB | Output is correct |
10 | Correct | 1 ms | 212 KB | Output is correct |
11 | Correct | 1 ms | 340 KB | Output is correct |
12 | Correct | 1 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 | 312 KB | Output is correct |
16 | Correct | 63 ms | 3588 KB | Output is correct |
17 | Correct | 64 ms | 3596 KB | Output is correct |
18 | Correct | 63 ms | 3684 KB | Output is correct |
19 | Correct | 67 ms | 3660 KB | Output is correct |
20 | Correct | 78 ms | 3640 KB | Output is correct |
21 | Correct | 99 ms | 9548 KB | Output is correct |
22 | Incorrect | 1 ms | 212 KB | Output isn't correct |
23 | Halted | 0 ms | 0 KB | - |