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
AC × 3
AC × 16
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