| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 796405 | 2023-07-28T11:15:10 Z | MadokaMagicaFan | Plus Minus (BOI17_plusminus) | C++14 | 164 ms | 14156 KB |
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
#define sz(v) ((int)(v.size()))
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) % md) << 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 - sz(cx)) << endl;
return 0;
}
if (hy == 1) {
// PRINTY:
cout << pw(n - sz(cy)) << endl;
return 0;
}
ll ans = (pw(m - sz(cx)) + pw(n - sz(cy)) - 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
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 0 ms | 212 KB | Output is correct |
| 2 | Correct | 0 ms | 212 KB | Output is correct |
| 3 | Correct | 0 ms | 212 KB | Output is correct |
| 4 | Correct | 0 ms | 260 KB | Output is correct |
| 5 | Correct | 0 ms | 212 KB | Output is correct |
| 6 | Correct | 0 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 |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 0 ms | 212 KB | Output is correct |
| 2 | Correct | 0 ms | 212 KB | Output is correct |
| 3 | Correct | 0 ms | 212 KB | Output is correct |
| 4 | Correct | 0 ms | 260 KB | Output is correct |
| 5 | Correct | 0 ms | 212 KB | Output is correct |
| 6 | Correct | 0 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 | 340 KB | Output is correct |
| 12 | Correct | 1 ms | 212 KB | Output is correct |
| 13 | Correct | 1 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 | 74 ms | 2716 KB | Output is correct |
| 17 | Correct | 64 ms | 2732 KB | Output is correct |
| 18 | Correct | 63 ms | 2728 KB | Output is correct |
| 19 | Correct | 68 ms | 2696 KB | Output is correct |
| 20 | Correct | 64 ms | 2700 KB | Output is correct |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 0 ms | 212 KB | Output is correct |
| 2 | Correct | 0 ms | 212 KB | Output is correct |
| 3 | Correct | 0 ms | 212 KB | Output is correct |
| 4 | Correct | 0 ms | 260 KB | Output is correct |
| 5 | Correct | 0 ms | 212 KB | Output is correct |
| 6 | Correct | 0 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 | 340 KB | Output is correct |
| 12 | Correct | 1 ms | 212 KB | Output is correct |
| 13 | Correct | 1 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 | 74 ms | 2716 KB | Output is correct |
| 17 | Correct | 64 ms | 2732 KB | Output is correct |
| 18 | Correct | 63 ms | 2728 KB | Output is correct |
| 19 | Correct | 68 ms | 2696 KB | Output is correct |
| 20 | Correct | 64 ms | 2700 KB | Output is correct |
| 21 | Correct | 123 ms | 8176 KB | Output is correct |
| 22 | Correct | 1 ms | 212 KB | Output is correct |
| 23 | Correct | 125 ms | 9576 KB | Output is correct |
| 24 | Correct | 100 ms | 9560 KB | Output is correct |
| 25 | Correct | 98 ms | 9588 KB | Output is correct |
| 26 | Correct | 118 ms | 11884 KB | Output is correct |
| 27 | Correct | 112 ms | 11880 KB | Output is correct |
| 28 | Correct | 109 ms | 11844 KB | Output is correct |
| 29 | Correct | 126 ms | 11880 KB | Output is correct |
| 30 | Correct | 164 ms | 14156 KB | Output is correct |