# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
208541 | 2020-03-11T13:26:49 Z | eriksuenderhauf | Plus Minus (BOI17_plusminus) | C++11 | 66 ms | 3576 KB |
//#pragma GCC optimize("O3") #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #define enl printf("\n") #define case(t) printf("Case #%d: ", (t)) #define ni(n) scanf("%d", &(n)) #define nl(n) scanf("%lld", &(n)) #define nai(a, n) for (int i = 0; i < (n); i++) ni(a[i]) #define nal(a, n) for (int i = 0; i < (n); i++) nl(a[i]) #define pri(n) printf("%d\n", (n)) #define prl(n) printf("%lld\n", (n)) #define pii pair<int, int> #define pil pair<int, long long> #define pll pair<long long, long long> #define vii vector<pii> #define vil vector<pil> #define vll vector<pll> #define vi vector<int> #define vl vector<long long> #define pb push_back #define mp make_pair #define fi first #define se second using namespace std; using namespace __gnu_pbds; typedef long long ll; typedef cc_hash_table<int,int,hash<int>> ht; typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> oset; const double pi = acos(-1); const int MOD = 1e9 + 7; const int INF = 1e9 + 7; const int MAXN = 1e5 + 5; const double eps = 1e-9; pair<pii,int> a[MAXN]; ll n, m; int fl = 0, k; ll pw(ll a, ll b) { ll ret = 1; while (b > 0) { if (b & 1) ret = (ret * a) % MOD, b--; else a = (a * a) % MOD, b /= 2ll; } return ret; } ll solve() { sort(a, a + k); ll cnt = 0; for (int i = 0; i < k; i++) { int j = i; while (j < k && a[i].fi.fi == a[j].fi.fi) j++; for (int l = i + 1; l < j; l++) { if ((a[l].fi.se + a[l].se) % 2 == (a[i].fi.se + a[i].se) % 2) continue; fl = 1; return 0; } cnt++; i = j - 1; } return pw(2, n - cnt); } int main() { scanf("%I64d %I64d %d", &n, &m, &k); for (int i = 0; i < k; i++) { char c; scanf(" %c %d %d", &c, &a[i].fi, &a[i].fi.se); if (c == '-') a[i].se = 1; else a[i].se = 0; } ll ans = solve(); swap(n, m); for (int i = 0; i < k; i++) swap(a[i].fi.fi, a[i].fi.se); ans = (ans + solve()) % MOD; if (!fl) { if (k) ans = (ans - 1 + MOD) % MOD; else ans = (ans - 2 + MOD) % MOD; } printf("%I64d\n", ans); }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 256 KB | Output is correct |
2 | Correct | 5 ms | 376 KB | Output is correct |
3 | Correct | 5 ms | 376 KB | Output is correct |
4 | Correct | 5 ms | 376 KB | Output is correct |
5 | Correct | 5 ms | 376 KB | Output is correct |
6 | Correct | 5 ms | 256 KB | Output is correct |
7 | Correct | 5 ms | 376 KB | Output is correct |
8 | Correct | 5 ms | 376 KB | Output is correct |
9 | Correct | 5 ms | 376 KB | Output is correct |
10 | Correct | 5 ms | 376 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 256 KB | Output is correct |
2 | Correct | 5 ms | 376 KB | Output is correct |
3 | Correct | 5 ms | 376 KB | Output is correct |
4 | Correct | 5 ms | 376 KB | Output is correct |
5 | Correct | 5 ms | 376 KB | Output is correct |
6 | Correct | 5 ms | 256 KB | Output is correct |
7 | Correct | 5 ms | 376 KB | Output is correct |
8 | Correct | 5 ms | 376 KB | Output is correct |
9 | Correct | 5 ms | 376 KB | Output is correct |
10 | Correct | 5 ms | 376 KB | Output is correct |
11 | Correct | 6 ms | 376 KB | Output is correct |
12 | Correct | 5 ms | 376 KB | Output is correct |
13 | Correct | 5 ms | 376 KB | Output is correct |
14 | Correct | 5 ms | 376 KB | Output is correct |
15 | Correct | 5 ms | 376 KB | Output is correct |
16 | Correct | 54 ms | 2424 KB | Output is correct |
17 | Correct | 55 ms | 2424 KB | Output is correct |
18 | Correct | 56 ms | 2400 KB | Output is correct |
19 | Correct | 55 ms | 2424 KB | Output is correct |
20 | Correct | 55 ms | 2424 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 256 KB | Output is correct |
2 | Correct | 5 ms | 376 KB | Output is correct |
3 | Correct | 5 ms | 376 KB | Output is correct |
4 | Correct | 5 ms | 376 KB | Output is correct |
5 | Correct | 5 ms | 376 KB | Output is correct |
6 | Correct | 5 ms | 256 KB | Output is correct |
7 | Correct | 5 ms | 376 KB | Output is correct |
8 | Correct | 5 ms | 376 KB | Output is correct |
9 | Correct | 5 ms | 376 KB | Output is correct |
10 | Correct | 5 ms | 376 KB | Output is correct |
11 | Correct | 6 ms | 376 KB | Output is correct |
12 | Correct | 5 ms | 376 KB | Output is correct |
13 | Correct | 5 ms | 376 KB | Output is correct |
14 | Correct | 5 ms | 376 KB | Output is correct |
15 | Correct | 5 ms | 376 KB | Output is correct |
16 | Correct | 54 ms | 2424 KB | Output is correct |
17 | Correct | 55 ms | 2424 KB | Output is correct |
18 | Correct | 56 ms | 2400 KB | Output is correct |
19 | Correct | 55 ms | 2424 KB | Output is correct |
20 | Correct | 55 ms | 2424 KB | Output is correct |
21 | Correct | 60 ms | 2808 KB | Output is correct |
22 | Correct | 5 ms | 376 KB | Output is correct |
23 | Correct | 59 ms | 2840 KB | Output is correct |
24 | Correct | 57 ms | 2808 KB | Output is correct |
25 | Correct | 63 ms | 2816 KB | Output is correct |
26 | Correct | 57 ms | 3192 KB | Output is correct |
27 | Correct | 55 ms | 3064 KB | Output is correct |
28 | Correct | 60 ms | 3064 KB | Output is correct |
29 | Correct | 55 ms | 3064 KB | Output is correct |
30 | Correct | 66 ms | 3576 KB | Output is correct |