# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
197337 | 2020-01-20T12:37:47 Z | dndhk | Plus Minus (BOI17_plusminus) | C++14 | 252 ms | 13416 KB |
#include <bits/stdc++.h> #define pb push_back using namespace std; typedef pair<int, int> pii; typedef long long ll; const int MAX_N = 200000; const int MAX_K = 18; const ll MOD = 1000000007; int N, M, K; struct S{ int type, x, y; }; vector<S> vt; ll ans; ll multi(ll x, ll y){ if(y==0) return 1; if(y==1) return x%MOD; ll m = multi(x, y/2); if(y%2){ return (m*m%MOD)*x%MOD; }return (m*m)%MOD; } map<int, int> mp; vector<int> v; void solve(){ while(!v.empty()){ mp[v.back()] = 0; v.pop_back(); } for(int i=0; i<vt.size(); i++){ S now = vt[i]; if(now.x%2==0){ now.type*=(-1); } if(mp[now.y]==0){ v.pb(now.y); mp[now.y] = now.type; }else if(mp[now.y]!=now.type){ return; } } ll two = multi(2LL, (ll)M - (ll)v.size()); ans = (ans + two) % MOD; } int main(){ scanf("%d%d%d", &N, &M, &K); for(int i=0; i<K; i++){ getchar(); char c; int a, b; scanf("%c %d %d", &c, &a, &b); if(c=='+'){ vt.pb({1, a, b}); }else{ vt.pb({-1, a, b}); } } solve(); for(int i=0; i<K; i++){ int tmp = vt[i].x; vt[i].x = vt[i].y; vt[i].y = tmp; } int tmp = N; N = M; M = tmp; solve(); bool tf1 = true, tf2 = true; for(int i=0; i<vt.size(); i++){ if((vt[i].x+vt[i].y+(vt[i].type+1)/2)%2){ tf1 = false; }else{ tf2 = false; } } if(tf1){ ans = (ans + MOD - 1) % MOD; }if(tf2){ ans = (ans + MOD - 1) % MOD; } cout<<ans; return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 504 KB | Output is correct |
2 | Correct | 2 ms | 256 KB | Output is correct |
3 | Correct | 2 ms | 256 KB | Output is correct |
4 | Correct | 2 ms | 256 KB | Output is correct |
5 | Correct | 2 ms | 256 KB | Output is correct |
6 | Correct | 2 ms | 376 KB | Output is correct |
7 | Correct | 2 ms | 376 KB | Output is correct |
8 | Correct | 2 ms | 376 KB | Output is correct |
9 | Correct | 2 ms | 376 KB | Output is correct |
10 | Correct | 2 ms | 376 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 504 KB | Output is correct |
2 | Correct | 2 ms | 256 KB | Output is correct |
3 | Correct | 2 ms | 256 KB | Output is correct |
4 | Correct | 2 ms | 256 KB | Output is correct |
5 | Correct | 2 ms | 256 KB | Output is correct |
6 | Correct | 2 ms | 376 KB | Output is correct |
7 | Correct | 2 ms | 376 KB | Output is correct |
8 | Correct | 2 ms | 376 KB | Output is correct |
9 | Correct | 2 ms | 376 KB | Output is correct |
10 | Correct | 2 ms | 376 KB | Output is correct |
11 | Correct | 3 ms | 376 KB | Output is correct |
12 | Correct | 2 ms | 256 KB | Output is correct |
13 | Correct | 2 ms | 256 KB | Output is correct |
14 | Correct | 2 ms | 376 KB | Output is correct |
15 | Correct | 2 ms | 376 KB | Output is correct |
16 | Correct | 31 ms | 2964 KB | Output is correct |
17 | Correct | 30 ms | 2928 KB | Output is correct |
18 | Correct | 31 ms | 2928 KB | Output is correct |
19 | Correct | 60 ms | 2928 KB | Output is correct |
20 | Correct | 61 ms | 2928 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 504 KB | Output is correct |
2 | Correct | 2 ms | 256 KB | Output is correct |
3 | Correct | 2 ms | 256 KB | Output is correct |
4 | Correct | 2 ms | 256 KB | Output is correct |
5 | Correct | 2 ms | 256 KB | Output is correct |
6 | Correct | 2 ms | 376 KB | Output is correct |
7 | Correct | 2 ms | 376 KB | Output is correct |
8 | Correct | 2 ms | 376 KB | Output is correct |
9 | Correct | 2 ms | 376 KB | Output is correct |
10 | Correct | 2 ms | 376 KB | Output is correct |
11 | Correct | 3 ms | 376 KB | Output is correct |
12 | Correct | 2 ms | 256 KB | Output is correct |
13 | Correct | 2 ms | 256 KB | Output is correct |
14 | Correct | 2 ms | 376 KB | Output is correct |
15 | Correct | 2 ms | 376 KB | Output is correct |
16 | Correct | 31 ms | 2964 KB | Output is correct |
17 | Correct | 30 ms | 2928 KB | Output is correct |
18 | Correct | 31 ms | 2928 KB | Output is correct |
19 | Correct | 60 ms | 2928 KB | Output is correct |
20 | Correct | 61 ms | 2928 KB | Output is correct |
21 | Correct | 159 ms | 6944 KB | Output is correct |
22 | Correct | 3 ms | 504 KB | Output is correct |
23 | Correct | 29 ms | 3184 KB | Output is correct |
24 | Correct | 34 ms | 3184 KB | Output is correct |
25 | Correct | 34 ms | 3184 KB | Output is correct |
26 | Correct | 97 ms | 7396 KB | Output is correct |
27 | Correct | 99 ms | 7324 KB | Output is correct |
28 | Correct | 148 ms | 9324 KB | Output is correct |
29 | Correct | 188 ms | 11300 KB | Output is correct |
30 | Correct | 252 ms | 13416 KB | Output is correct |