結果
問題 | No.2595 Parsing Challenge |
ユーザー | 👑 hos.lyric |
提出日時 | 2023-12-23 00:27:07 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 10,832 bytes |
コンパイル時間 | 3,150 ms |
コンパイル使用メモリ | 158,916 KB |
実行使用メモリ | 43,684 KB |
最終ジャッジ日時 | 2024-09-27 11:43:15 |
合計ジャッジ時間 | 13,593 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 14 ms
34,944 KB |
testcase_01 | AC | 14 ms
35,068 KB |
testcase_02 | AC | 15 ms
34,968 KB |
testcase_03 | AC | 14 ms
35,548 KB |
testcase_04 | AC | 13 ms
34,944 KB |
testcase_05 | AC | 15 ms
35,016 KB |
testcase_06 | AC | 14 ms
35,900 KB |
testcase_07 | AC | 13 ms
34,788 KB |
testcase_08 | AC | 13 ms
35,268 KB |
testcase_09 | AC | 13 ms
34,828 KB |
testcase_10 | AC | 14 ms
34,872 KB |
testcase_11 | AC | 14 ms
34,732 KB |
testcase_12 | AC | 14 ms
35,152 KB |
testcase_13 | AC | 14 ms
34,864 KB |
testcase_14 | AC | 14 ms
34,904 KB |
testcase_15 | AC | 14 ms
35,796 KB |
testcase_16 | AC | 14 ms
34,992 KB |
testcase_17 | AC | 15 ms
35,096 KB |
testcase_18 | AC | 14 ms
35,232 KB |
testcase_19 | AC | 13 ms
34,988 KB |
testcase_20 | AC | 17 ms
34,876 KB |
testcase_21 | AC | 16 ms
34,904 KB |
testcase_22 | AC | 16 ms
34,920 KB |
testcase_23 | AC | 15 ms
34,952 KB |
testcase_24 | AC | 16 ms
35,036 KB |
testcase_25 | AC | 39 ms
35,296 KB |
testcase_26 | AC | 42 ms
35,068 KB |
testcase_27 | AC | 41 ms
35,228 KB |
testcase_28 | AC | 42 ms
35,008 KB |
testcase_29 | AC | 42 ms
35,028 KB |
testcase_30 | AC | 279 ms
36,448 KB |
testcase_31 | AC | 280 ms
36,092 KB |
testcase_32 | AC | 283 ms
36,424 KB |
testcase_33 | AC | 305 ms
36,680 KB |
testcase_34 | AC | 280 ms
36,480 KB |
testcase_35 | TLE | - |
testcase_36 | -- | - |
testcase_37 | -- | - |
testcase_38 | -- | - |
testcase_39 | -- | - |
testcase_40 | -- | - |
testcase_41 | -- | - |
testcase_42 | -- | - |
testcase_43 | -- | - |
testcase_44 | -- | - |
testcase_45 | -- | - |
testcase_46 | -- | - |
testcase_47 | -- | - |
testcase_48 | -- | - |
testcase_49 | -- | - |
testcase_50 | -- | - |
testcase_51 | -- | - |
testcase_52 | -- | - |
testcase_53 | -- | - |
testcase_54 | -- | - |
testcase_55 | -- | - |
testcase_56 | -- | - |
testcase_57 | -- | - |
testcase_58 | -- | - |
testcase_59 | -- | - |
ソースコード
#include <cassert>#include <cmath>#include <cstdint>#include <cstdio>#include <cstdlib>#include <cstring>#include <algorithm>#include <bitset>#include <complex>#include <deque>#include <functional>#include <iostream>#include <limits>#include <map>#include <numeric>#include <queue>#include <random>#include <set>#include <sstream>#include <string>#include <unordered_map>#include <unordered_set>#include <utility>#include <vector>using namespace std;using Int = long long;template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };template <class T> ostream &operator<<(ostream &os, const vector<T> &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i>= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; }template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }#define COLOR(s) ("\x1b[" s "m")// https://github.com/SSRS-cp/yuki2595-bigint-lib////////////////////////////////////////////////////////////////////////////////#include <vector>#include <string>#include <atcoder/convolution>const int DIGIT = 6;const int BASE = 1000000;struct positive_bigint{std::vector<int> d;positive_bigint(){}positive_bigint(long long X){while (X > 0){d.push_back(X % BASE);X /= BASE;}}positive_bigint(std::string S){if (S == "0"){S = "";}int L = S.size();d.resize((L + DIGIT - 1) / DIGIT, 0);for (int i = L - 1; i >= 0; i -= 6){for (int j = std::max(i - 5, 0); j <= i; j++){d[i / DIGIT] *= 10;d[i / DIGIT] += S[j] - '0';}}std::reverse(d.begin(), d.end());}bool empty() const {return d.empty();}int size() const {return d.size();}int& operator [](int i){return d[i];}int operator [](int i) const {return d[i];}};std::string to_string(const positive_bigint &A){int N = A.size();std::string ans;for (int i = N - 1; i >= 0; i--){std::string tmp = std::to_string(A[i]);if (i < N - 1){ans += std::string(DIGIT - tmp.size(), '0');}ans += tmp;}if (ans.empty()){ans = "0";}return ans;}std::istream& operator >>(std::istream &is, positive_bigint &A){std::string S;is >> S;A = positive_bigint(S);return is;}std::ostream& operator <<(std::ostream &os, positive_bigint &A){os << to_string(A);return os;}int cmp(const positive_bigint &A, const positive_bigint &B){int N = A.size();int M = B.size();if (N < M){return -1;} else if (N > M){return 1;} else {for (int i = N - 1; i >= 0; i--){if (A[i] < B[i]){return -1;}if (A[i] > B[i]){return 1;}}return 0;}}bool operator ==(const positive_bigint &A, const positive_bigint &B){return cmp(A, B) == 0;}bool operator !=(const positive_bigint &A, const positive_bigint &B){return cmp(A, B) != 0;}bool operator <(const positive_bigint &A, const positive_bigint &B){return cmp(A, B) < 0;}bool operator >(const positive_bigint &A, const positive_bigint &B){return cmp(A, B) > 0;}bool operator <=(const positive_bigint &A, const positive_bigint &B){return cmp(A, B) <= 0;}bool operator >=(const positive_bigint &A, const positive_bigint &B){return cmp(A, B) >= 0;}positive_bigint& operator +=(positive_bigint &A, const positive_bigint &B){int N = A.size();int M = B.size();while (N < M){A.d.push_back(0);N++;}for (int i = 0; i < M; i++){A[i] += B[i];}for (int i = 0; i < N - 1; i++){if (A[i] >= BASE){A[i] -= BASE;A[i + 1]++;}}if (N > 0){if (A[N - 1] >= BASE){A.d.push_back(1);A[N - 1] -= BASE;}}return A;}positive_bigint operator +(const positive_bigint &A, const positive_bigint &B){positive_bigint A2 = A;A2 += B;return A2;}positive_bigint& operator -=(positive_bigint &A, const positive_bigint &B){int N = A.size();int M = B.size();for (int i = 0; i < M; i++){A[i] -= B[i];}for (int i = 0; i < N - 1; i++){if (A[i] < 0){A[i] += BASE;A[i + 1]--;}}while (!A.empty()){if (A.d.back() == 0){A.d.pop_back();} else {break;}}return A;}positive_bigint operator -(const positive_bigint &A, const positive_bigint &B){positive_bigint A2 = A;A2 -= B;return A2;}positive_bigint operator *(const positive_bigint &A, const positive_bigint &B){if (A.empty() || B.empty()){return 0;}int N = A.size();int M = B.size();std::vector<long long> a(N);for (int i= 0; i < N; i++){a[i] = A[i];}std::vector<long long> b(M);for (int i = 0; i < M; i++){b[i] = B[i];}std::vector<long long> C = atcoder::convolution_ll(a, b);for (int i = 0; i < N + M - 2; i++){C[i + 1] += C[i] / BASE;C[i] %= BASE;}if (C[N + M - 2] >= BASE){C.resize(N + M);C[N + M - 1] += C[N + M - 2] / BASE;C[N + M - 2] %= BASE;}positive_bigint ans;ans.d.resize(C.size());for (int i = 0; i < C.size(); i++){ans[i] = C[i];}return ans;}positive_bigint operator *=(positive_bigint &A, const positive_bigint &B){A = A * B;return A;}struct bigint{bool neg = false;positive_bigint a;bigint(){}bigint(long long X): neg(X < 0), a(abs(X)){}bigint(const positive_bigint &X, bool neg = false): neg(neg), a(X){}bigint(const std::string &s){if (!s.empty()){if (s[0] == '-'){neg = true;a = positive_bigint(s.substr(1, s.size() - 1));} else {a = positive_bigint(s);}}}bool empty() const {return a.empty();}int size() const {return a.size();}int& operator [](int i){return a[i];}};std::string to_string(const bigint &A){std::string ans;if (A.neg){ans += '-';}ans += to_string(A.a);return ans;}std::istream& operator >>(std::istream &is, bigint &A){std::string S;is >> S;if (S != "0"){A = bigint(S);}return is;}std::ostream& operator <<(std::ostream &os, bigint A){os << to_string(A);return os;}positive_bigint abs(const bigint &A){return A.a;}int cmp(const bigint &A, const bigint &B){if (!A.neg){if (!B.neg){return cmp(A.a, B.a);} else {return 1;}} else {if (!B.neg){return -1;} else {return cmp(B.a, A.a);}}}bool operator ==(const bigint &A, const bigint &B){return cmp(A, B) == 0;}bool operator !=(const bigint &A, const bigint &B){return cmp(A, B) != 0;}bool operator <(const bigint &A, const bigint &B){return cmp(A, B) < 0;}bool operator >(const bigint &A, const bigint &B){return cmp(A, B) > 0;}bool operator <=(const bigint &A, const bigint &B){return cmp(A, B) <= 0;}bool operator >=(const bigint &A, const bigint &B){return cmp(A, B) >= 0;}bigint operator +(const bigint &A){return A;}bigint operator -(const bigint &A){bigint A2 = A;if (!A2.empty()){A2.neg = !A2.neg;}return A2;}bigint& operator +=(bigint &A, const bigint &B){if (A.neg == B.neg){A.a += B.a;} else {int c = cmp(A.a, B.a);if (c > 0){A.a -= B.a;} else if (c < 0){A.a = B.a - A.a;A.neg = !A.neg;} else {A = 0;}}return A;}bigint operator +(const bigint &A, const bigint &B){bigint A2 = A;A2 += B;return A2;}bigint& operator -=(bigint &A, const bigint &B){if (A.neg != B.neg){A.a += B.a;} else {int c = cmp(A.a, B.a);if (c > 0){A.a -= B.a;} else if (c < 0){A.a = B.a - A.a;A.neg = !A.neg;} else {A = 0;}}return A;}bigint operator -(const bigint &A, const bigint &B){bigint A2 = A;A2 -= B;return A2;}bigint operator *=(bigint &A, const bigint &B){if (A.empty() || B.empty()){A = 0;} else {if (B.neg){A.neg = !A.neg;}A.a *= B.a;}return A;}bigint operator *(const bigint &A, const bigint &B){bigint A2 = A;A2 *= B;return A2;}////////////////////////////////////////////////////////////////////////////////void swap(positive_bigint &a, positive_bigint &b) {a.d.swap(b.d);}void swap(bigint &a, bigint &b) {swap(a.neg, b.neg);swap(a.a, b.a);}#define negate negate__void negate(bigint &a) {if (!a.empty()) {a.neg = !a.neg;}}int N;char S[1'000'010];int ssLen;string ss[1'000'010];struct Data {bigint a, b;int i;bigint eval() const {return a * bigint(ss[i]) + b;}// destroy fvoid operator+=(Data &f) {if (ss[i].size() > ss[f.i].size()) {swap(a, f.a);swap(b, f.b);swap(i, f.i);}const bigint c = f.eval();b += c;}void operator-=(Data &f) {if (ss[i].size() > ss[f.i].size()) {swap(a, f.a);swap(b, f.b);swap(i, f.i);negate(a);negate(b);negate(f.a);negate(f.b);}const bigint c = f.eval();b -= c;}void operator*=(Data &f) {if (ss[i].size() > ss[f.i].size()) {swap(a, f.a);swap(b, f.b);swap(i, f.i);}const bigint c = f.eval();a *= c;b *= c;}};int cur;void eat(char c) {assert(S[cur] == c);++cur;}Data expr();Data term();Data fact();Data expr() {Data ret = term();for (; S[cur] == '+' || S[cur] == '-'; ) {const char op = S[cur++];Data res = term();switch (op) {case '+': ret += res; break;case '-': ret -= res; break;default: assert(false);}}return ret;}Data term() {Data ret = fact();for (; S[cur] == '*'; ) {const char op = S[cur++];Data res = fact();switch (op) {case '*': ret *= res; break;default: assert(false);}}return ret;}Data fact() {Data ret;if (S[cur] == '(') {eat('(');ret = expr();eat(')');} else {int sig = +1;for (; S[cur] == '-'; ) {eat('-');sig = -sig;}assert(isdigit(S[cur]));const int i = ssLen++;ss[i] = "";if (sig < 0) {ss[i] += "-";}for (; isdigit(S[cur]); ) {ss[i] += S[cur++];}ret = Data{bigint(1), bigint(0), i};}return ret;}int main() {for (; ~scanf("%d", &N); ) {scanf("%s", S);cur = 0;ssLen = 0;const bigint ans = expr().eval();cout << ans << endl;}return 0;}