This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub ebi-fly13/icpc_library
#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1300" #include "../../template/template.hpp" #include "../../template/parsing_template.hpp" #include "../../math/gauss_jordan.hpp" #include "../../utility/rational.hpp" using namespace lib; std::vector<std::vector<rational>> chemical_equation(State &); std::vector<std::map<std::string, ll>> molecule_sequence(State &); std::map<std::string, ll> molecule(State &); std::map<std::string, ll> group(State &); std::map<std::string, ll> unit_group(State &); std::pair<std::string, ll> chemical_element(State &); ll number(State &); std::vector<std::vector<rational>> chemical_equation(State &begin) { auto lhs = molecule_sequence(begin); consume(begin, '-'); consume(begin, '>'); auto rhs = molecule_sequence(begin); std::set<std::string> set; for (auto &map : lhs) { for (auto &p : map) set.insert(p.first); } int h = set.size(); std::vector a(h, std::vector<rational>()); rep(i, 0, lhs.size()) { int j = 0; for (auto &s : set) { a[j].emplace_back(lhs[i][s]); j++; } } rep(i, 0, rhs.size()) { int j = 0; for (auto &s : set) { a[j].emplace_back(-rhs[i][s]); j++; } } assert(a[0].size() == lhs.size() + rhs.size()); return a; } std::vector<std::map<std::string, ll>> molecule_sequence(State &begin) { std::vector<std::map<std::string, ll>> mole; mole.emplace_back(molecule(begin)); while (expect(begin, '+')) { consume(begin, '+'); mole.emplace_back(molecule(begin)); } return mole; } std::map<std::string, ll> molecule(State &begin) { auto ret = group(begin); while (isAlpha(*begin) || expect(begin, '(')) { for (auto [s, c] : group(begin)) { ret[s] += c; } } return ret; } std::map<std::string, ll> group(State &begin) { auto ret = unit_group(begin); if (isdigit(*begin)) { ll num = number(begin); for (auto &p : ret) { p.second *= num; } } return ret; } std::map<std::string, ll> unit_group(State &begin) { if (isAlpha(*begin)) { std::string ret = ""; ret += *begin; consume(begin, *begin); if (isalpha(*begin)) { ret += *begin; consume(begin, *begin); } std::map<std::string, ll> map; map[ret] = 1; return map; } else { consume(begin, '('); auto ret = molecule(begin); consume(begin, ')'); return ret; } } ll number(State &begin) { ll ret = 0; while (isdigit(*begin)) { ret *= 10; ret += *begin - '0'; consume(begin, *begin); } return ret; } int main() { std::string s; while (std::cin >> s, !(s == ".")) { State begin = s.begin(); auto a = chemical_equation(begin); consume(begin, '.'); a = gauss_jordan<rational>(a); int n = a.size(); int m = a[0].size(); int x = -1; { bool is_break = false; rrep(i, 0, n) { if(is_break) break; rep(j, 0, m) { if (a[i][j] != 0) { x = j + 1; is_break = true; break; } } } } std::vector<ll> ans(m, 1); rep(j,x,m) { rep(i,0,n) { if(a[i][j] != 0) { ans[j] = std::lcm(ans[j], a[i][j].val().second); } } } rep(i,0,x) { ans[i] = 0; rep(j,x,m) { ans[i] -= (a[i][j] * ans[j]).val().first; } } rep(i,0,m) { std::cout << ans[i] << " \n"[i == m-1]; } } }
#line 1 "test/others/aoj_1300.test.cpp" #define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1300" #line 2 "template/template.hpp" #include <bits/stdc++.h> #define rep(i, s, n) for (int i = (int)(s); i < (int)(n); i++) #define rrep(i, s, n) for (int i = (int)(n)-1; i >= (int)(s); i--) #define all(v) v.begin(), v.end() using ll = long long; using ld = long double; using ull = unsigned long long; template <typename T> bool chmin(T &a, const T &b) { if (a <= b) return false; a = b; return true; } template <typename T> bool chmax(T &a, const T &b) { if (a >= b) return false; a = b; return true; } namespace lib { using namespace std; } // namespace lib // using namespace lib; #line 2 "template/parsing_template.hpp" #line 4 "template/parsing_template.hpp" namespace lib { typedef std::string::const_iterator State; bool expect(State &begin, char expected) { return *begin == expected; } void consume(State &begin, char expected) { assert(*begin == expected); begin++; } bool isdigit(char c) { return '0' <= c && c <= '9'; } bool isAlpha(char c) { return 'A' <= c && c <= 'Z'; } bool isalpha(char c) { return 'a' <= c && c <= 'z'; } } // namespace lib #line 3 "math/gauss_jordan.hpp" namespace lib { using namespace std; template <typename T> vector<vector<T>> gauss_jordan(vector<vector<T>> &a) { int n = a.size(); int m = a[0].size(); vector<vector<T>> b = a; int piv = 0; rep(j, 0, m) rep(i, piv, n) { if (b[i][j] != T(0)) { swap(b[i], b[piv]); T ip = T(1) / b[piv][j]; rep(l, 0, n) { if (l != piv) { T tmp = ip * b[l][j]; rep(k, j, m) b[l][k] -= tmp * b[piv][k]; } } rep(k, j, m) b[piv][k] *= ip; piv++; break; } } return b; } } // namespace lib #line 2 "utility/rational.hpp" #line 4 "utility/rational.hpp" namespace lib { struct rational { rational() : p(0), q(1) {} rational(ll n) : p(n), q(1) {} rational(ll n, ll m) { assert(m != 0); if (m < 0) n = -n, m = -m; ll g = gcd(n, m); p = n / g; q = m / g; } explicit operator const ld () const { return ld(p) / ld(q); } rational& operator+=(const rational& rhs){ ll g = gcd(q, rhs.q); ll np = rhs.q / g * p + q / g * rhs.p; ll nq = q / g * rhs.q; ll ng = gcd(np, nq); p = np / ng, q = nq / ng; return *this; } rational& operator-=(const rational& rhs) { (*this) += rational(-rhs.p, rhs.q); return *this; } rational& operator*=(const rational& rhs) { ll g1 = gcd(q, rhs.p), g2 = gcd(p, rhs.q); ll np = p / g2 * rhs.p / g1; ll nq = q / g1 * rhs.q / g2; p = np, q = nq; return *this; } rational& operator/=(const rational& rhs) { (*this) *= rational(rhs.q, rhs.p); return *this; } rational operator+() const { return *this; } rational operator-() const { return rational() - *this; } friend rational operator+(const rational& lhs, const rational& rhs) { return rational(lhs) += rhs; } friend rational operator-(const rational& lhs, const rational& rhs) { return rational(lhs) -= rhs; } friend rational operator*(const rational& lhs, const rational& rhs) { return rational(lhs) *= rhs; } friend rational operator/(const rational& lhs, const rational& rhs) { return rational(lhs) /= rhs; } friend bool operator==(const rational& lhs, const rational& rhs) { return lhs.p == rhs.p && lhs.q == rhs.q; } friend bool operator!=(const rational& lhs, const rational& rhs) { return lhs.p != rhs.p || lhs.q != rhs.q; } friend bool operator<(const rational lhs, const rational rhs) { return less_than(lhs, rhs); } friend bool operator>(const rational lhs, const rational rhs) { return less_than(rhs, lhs); } friend bool operator<=(const rational lhs, const rational rhs) { return lhs == rhs || lhs < rhs; } friend bool operator>=(const rational lhs, const rational rhs) { return lhs == rhs || lhs > rhs; } friend std::ostream& operator<<(std::ostream& os, const rational& r) { return os << r.p << " / " << r.q; } std::pair<ll,ll> val() const { return {p, q}; } private: ll p, q; static bool less_than(rational lhs, rational rhs) { __int128_t lv = __int128_t(lhs.p) * __int128_t(rhs.q); __int128_t rv = __int128_t(lhs.q) * __int128_t(rhs.p); return lv < rv; } }; } // namespace lib #line 7 "test/others/aoj_1300.test.cpp" using namespace lib; std::vector<std::vector<rational>> chemical_equation(State &); std::vector<std::map<std::string, ll>> molecule_sequence(State &); std::map<std::string, ll> molecule(State &); std::map<std::string, ll> group(State &); std::map<std::string, ll> unit_group(State &); std::pair<std::string, ll> chemical_element(State &); ll number(State &); std::vector<std::vector<rational>> chemical_equation(State &begin) { auto lhs = molecule_sequence(begin); consume(begin, '-'); consume(begin, '>'); auto rhs = molecule_sequence(begin); std::set<std::string> set; for (auto &map : lhs) { for (auto &p : map) set.insert(p.first); } int h = set.size(); std::vector a(h, std::vector<rational>()); rep(i, 0, lhs.size()) { int j = 0; for (auto &s : set) { a[j].emplace_back(lhs[i][s]); j++; } } rep(i, 0, rhs.size()) { int j = 0; for (auto &s : set) { a[j].emplace_back(-rhs[i][s]); j++; } } assert(a[0].size() == lhs.size() + rhs.size()); return a; } std::vector<std::map<std::string, ll>> molecule_sequence(State &begin) { std::vector<std::map<std::string, ll>> mole; mole.emplace_back(molecule(begin)); while (expect(begin, '+')) { consume(begin, '+'); mole.emplace_back(molecule(begin)); } return mole; } std::map<std::string, ll> molecule(State &begin) { auto ret = group(begin); while (isAlpha(*begin) || expect(begin, '(')) { for (auto [s, c] : group(begin)) { ret[s] += c; } } return ret; } std::map<std::string, ll> group(State &begin) { auto ret = unit_group(begin); if (isdigit(*begin)) { ll num = number(begin); for (auto &p : ret) { p.second *= num; } } return ret; } std::map<std::string, ll> unit_group(State &begin) { if (isAlpha(*begin)) { std::string ret = ""; ret += *begin; consume(begin, *begin); if (isalpha(*begin)) { ret += *begin; consume(begin, *begin); } std::map<std::string, ll> map; map[ret] = 1; return map; } else { consume(begin, '('); auto ret = molecule(begin); consume(begin, ')'); return ret; } } ll number(State &begin) { ll ret = 0; while (isdigit(*begin)) { ret *= 10; ret += *begin - '0'; consume(begin, *begin); } return ret; } int main() { std::string s; while (std::cin >> s, !(s == ".")) { State begin = s.begin(); auto a = chemical_equation(begin); consume(begin, '.'); a = gauss_jordan<rational>(a); int n = a.size(); int m = a[0].size(); int x = -1; { bool is_break = false; rrep(i, 0, n) { if(is_break) break; rep(j, 0, m) { if (a[i][j] != 0) { x = j + 1; is_break = true; break; } } } } std::vector<ll> ans(m, 1); rep(j,x,m) { rep(i,0,n) { if(a[i][j] != 0) { ans[j] = std::lcm(ans[j], a[i][j].val().second); } } } rep(i,0,x) { ans[i] = 0; rep(j,x,m) { ans[i] -= (a[i][j] * ans[j]).val().first; } } rep(i,0,m) { std::cout << ans[i] << " \n"[i == m-1]; } } }