Submission #2406690
Source Code Expand
#include <stack> #include <string> #include <vector> #include <iostream> #include <algorithm> using namespace std; const int mod = 998244353; int main() { string s; cin >> s; int pl = -1; vector<string> fixer; for (int i = 0; i < s.size(); i++) { if ('0' <= s[i] && s[i] <= '9') { if (pl == -1) pl = i; if (i == s.size() - 1 || !('0' <= s[i + 1] && s[i + 1] <= '9')) { fixer.push_back("("); fixer.push_back(s.substr(pl, i - pl + 1)); fixer.push_back(")"); } } else { fixer.push_back(string(1, s[i])); pl = -1; } } vector<vector<int> > g(1); vector<string> node(1); stack<int> st({ 0 }); for (int i = 0; i < fixer.size(); i++) { if (fixer[i] == "(") { g[st.top()].push_back(g.size()); st.push(g.size()); g.push_back(vector<int>()); node.push_back(""); } else if (fixer[i] == ")") { st.pop(); } else { node[st.top()] = fixer[i]; } } vector<vector<int> > dp(node.size()); for (int i = node.size() - 1; i >= 1; i--) { if (node[i] == "*") { vector<int> lv = dp[g[i][0]]; vector<int> rv = dp[g[i][1]]; if (lv.size() > rv.size()) { swap(lv, rv); } if (lv.size() == 1 && rv.size() == 1) { dp[i].push_back(1LL * lv[0] * rv[0] % mod); } if (lv.size() == 1 && rv.size() == 2) { dp[i].push_back(1LL * lv[0] * rv[0] % mod); dp[i].push_back(1LL * lv[0] * rv[1] % mod); } if (lv.size() == 2 && rv.size() == 2) { dp[i].push_back((1LL * lv[0] * rv[0] + 1LL * lv[1] * rv[1]) % mod); } } else if (node[i] == ",") { dp[i].push_back(dp[g[i][0]][0]); dp[i].push_back(dp[g[i][1]][0]); } else { int cur = 0; for (int j = 0; j < node[i].size(); j++) { cur = (10LL * cur + (node[i][j] - '0')) % mod; } dp[i].push_back(cur); } } cout << dp[1][0] << "\n"; return 0; }
Submission Info
Submission Time | |
---|---|
Task | E - ベクトル式 |
User | square1001 |
Language | C++14 (GCC 5.4.1) |
Score | 1 |
Code Size | 1880 Byte |
Status | AC |
Exec Time | 35 ms |
Memory | 14448 KB |
Judge Result
Set Name | sample | all | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 1 / 1 | ||||
Status |
|
|
Set Name | Test Cases |
---|---|
sample | sample-01.txt, sample-02.txt, sample-03.txt |
all | sample-01.txt, sample-02.txt, sample-03.txt, 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt, sample-01.txt, sample-02.txt, sample-03.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
01-01.txt | AC | 1 ms | 256 KB |
01-02.txt | AC | 1 ms | 256 KB |
01-03.txt | AC | 2 ms | 384 KB |
01-04.txt | AC | 4 ms | 1664 KB |
01-05.txt | AC | 34 ms | 14448 KB |
01-06.txt | AC | 33 ms | 14448 KB |
01-07.txt | AC | 35 ms | 14448 KB |
01-08.txt | AC | 35 ms | 14448 KB |
01-09.txt | AC | 1 ms | 256 KB |
01-10.txt | AC | 5 ms | 512 KB |
sample-01.txt | AC | 1 ms | 256 KB |
sample-02.txt | AC | 1 ms | 256 KB |
sample-03.txt | AC | 1 ms | 256 KB |