# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
129605 | 2019-07-12T18:58:42 Z | SamAnd | Plus Minus (BOI17_plusminus) | C++17 | 582 ms | 524292 KB |
#include <bits/stdc++.h> using namespace std; const int M = 1000000007, N = 1003; int ast(int x, int n) { if (n == 0) return 1; if (n % 2 == 0) { int y = ast(x, n / 2); return (y * 1LL * y) % M; } else { int y = ast(x, n - 1); return (x * 1LL * y) % M; } } int ans0, ans1; int n, m, k; map<int, vector<int> > sp0, sm0; set<int> z1, z2; set<int> sp, sm; int dp[N][2][2]; int main() { //freopen("input.txt", "r", stdin); scanf("%d%d%d", &n, &m, &k); for (int i = 0; i < k; ++i) { char ty; int x, y; scanf(" %c%d%d", &ty, &x, &y); if (ty == '-') sm0[x].push_back(y); else sp0[x].push_back(y); if (x % 2 == 1) { if (ty == '+') sp.insert(y); else sm.insert(y); } else { if (ty == '-') sp.insert(y); else sm.insert(y); } } // count ans0 ans0 = 1; for (map<int, vector<int> >::iterator it = sp0.begin(); it != sp0.end(); ++it) { vector<int> v = it->second; for (int i = 0; i < v.size(); ++i) { if (v[i] % 2 == 0) z1.insert(it->first); else z2.insert(it->first); } } for (map<int, vector<int> >::iterator it = sm0.begin(); it != sm0.end(); ++it) { vector<int> v = it->second; for (int i = 0; i < v.size(); ++i) { if (v[i] % 2 == 1) z1.insert(it->first); else z2.insert(it->first); } } for (set<int>::iterator it = z1.begin(); it != z1.end(); ++it) { if (z2.find((*it)) != z2.end()) { ans0 = 0; break; } } ans0 = (ans0 * 1LL * ast(2, n - z1.size() - z2.size())); //count ans1 if (sm.find(1) != sm.end()) dp[1][0][0] = 1; else if (sp.find(1) != sp.end()) dp[1][1][0] = 1; else { dp[1][0][0] = 1; dp[1][1][0] = 1; } for (int i = 1; i < m; ++i) { if (sm.find(i + 1) != sm.end()) { dp[i + 1][0][1] += dp[i][0][0]; //dp[i + 1][1][0] += dp[i][0][0]; dp[i + 1][0][0] += dp[i][1][0]; //dp[i + 1][1][1] += dp[i][1][0]; dp[i + 1][0][1] += dp[i][0][1]; //dp[i + 1][1][1] += dp[i][0][1]; dp[i + 1][0][1] += dp[i][1][1]; //dp[i + 1][1][1] += dp[i][1][1]; } else if (sp.find(i + 1) != sp.end()) { //dp[i + 1][0][1] += dp[i][0][0]; dp[i + 1][1][0] += dp[i][0][0]; //dp[i + 1][0][0] += dp[i][1][0]; dp[i + 1][1][1] += dp[i][1][0]; //dp[i + 1][0][1] += dp[i][0][1]; dp[i + 1][1][1] += dp[i][0][1]; //dp[i + 1][0][1] += dp[i][1][1]; dp[i + 1][1][1] += dp[i][1][1]; } else { dp[i + 1][0][1] += dp[i][0][0]; dp[i + 1][1][0] += dp[i][0][0]; dp[i + 1][0][0] += dp[i][1][0]; dp[i + 1][1][1] += dp[i][1][0]; dp[i + 1][0][1] += dp[i][0][1]; dp[i + 1][1][1] += dp[i][0][1]; dp[i + 1][0][1] += dp[i][1][1]; dp[i + 1][1][1] += dp[i][1][1]; } dp[i + 1][0][0] %= M; dp[i + 1][0][1] %= M; dp[i + 1][1][0] %= M; dp[i + 1][1][1] %= M; } ans1 = (dp[m][1][1] + dp[m][0][1]) % M; for (int y = 1; y <= m; ++y) { if (sm.find(y) != sm.end() && sp.find(y) != sp.end()) ans1 = 0; } cout << (ans0 + ans1) % M << endl; return 0; }
Compilation message
# | 결과 | 실행 시간 | 메모리 | 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 | 376 KB | Output is correct |
5 | Runtime error | 582 ms | 524292 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
6 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | 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 | 376 KB | Output is correct |
5 | Runtime error | 582 ms | 524292 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
6 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | 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 | 376 KB | Output is correct |
5 | Runtime error | 582 ms | 524292 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
6 | Halted | 0 ms | 0 KB | - |