結果

問題 No.2595 Parsing Challenge
ユーザー 👑 hos.lyrichos.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 -- -
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#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 f
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();
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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0