#939860 (C++23) No.2595 Parsing Challenge

提出ソース

結果

問題	No.2595 Parsing Challenge
ユーザー	MtSaka
提出日時	2023-12-23 00:34:41
言語	C++23 (gcc 12.3.0 + boost 1.83.0)
結果	TLE
実行時間	-
コード長	20,138 bytes
コンパイル時間	7,994 ms
コンパイル使用メモリ	344,580 KB
実行使用メモリ	351,256 KB
最終ジャッジ日時	2023-12-23 00:35:23
合計ジャッジ時間	40,602 ms
ジャッジサーバーID （参考情報）	judge15 / judge11

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,676 KB
testcase_01	AC	2 ms 6,676 KB
testcase_02	AC	2 ms 6,676 KB
testcase_03	AC	2 ms 6,676 KB
testcase_04	AC	2 ms 6,676 KB
testcase_05	AC	2 ms 6,676 KB
testcase_06	AC	2 ms 6,676 KB
testcase_07	AC	4 ms 6,676 KB
testcase_08	AC	3 ms 6,676 KB
testcase_09	AC	2 ms 6,676 KB
testcase_10	AC	2 ms 6,676 KB
testcase_11	AC	2 ms 6,676 KB
testcase_12	AC	2 ms 6,676 KB
testcase_13	AC	2 ms 6,676 KB
testcase_14	AC	2 ms 6,676 KB
testcase_15	AC	2 ms 6,676 KB
testcase_16	AC	2 ms 6,676 KB
testcase_17	AC	2 ms 6,676 KB
testcase_18	AC	2 ms 6,676 KB
testcase_19	AC	2 ms 6,676 KB
testcase_20	AC	4 ms 6,676 KB
testcase_21	AC	4 ms 6,676 KB
testcase_22	AC	3 ms 6,676 KB
testcase_23	AC	3 ms 6,676 KB
testcase_24	AC	4 ms 6,676 KB
testcase_25	AC	16 ms 6,676 KB
testcase_26	AC	18 ms 6,676 KB
testcase_27	AC	18 ms 6,676 KB
testcase_28	AC	18 ms 6,676 KB
testcase_29	AC	18 ms 6,676 KB
testcase_30	AC	147 ms 6,676 KB
testcase_31	AC	151 ms 6,676 KB
testcase_32	AC	155 ms 6,676 KB
testcase_33	AC	158 ms 6,676 KB
testcase_34	AC	152 ms 6,676 KB
testcase_35	AC	1,002 ms 29,788 KB
testcase_36	AC	997 ms 31,580 KB
testcase_37	AC	1,005 ms 29,788 KB
testcase_38	AC	975 ms 30,044 KB
testcase_39	AC	1,009 ms 29,660 KB
testcase_40	AC	19 ms 8,512 KB
testcase_41	AC	19 ms 8,512 KB
testcase_42	AC	19 ms 8,512 KB
testcase_43	AC	264 ms 254,420 KB
testcase_44	AC	116 ms 6,676 KB
testcase_45	AC	114 ms 6,676 KB
testcase_46	AC	115 ms 6,676 KB
testcase_47	AC	114 ms 6,676 KB
testcase_48	AC	113 ms 6,676 KB
testcase_49	AC	640 ms 9,180 KB
testcase_50	AC	618 ms 9,164 KB
testcase_51	AC	613 ms 8,520 KB
testcase_52	AC	2,689 ms 9,816 KB
testcase_53	AC	2,764 ms 9,812 KB
testcase_54	AC	2,628 ms 9,684 KB
testcase_55	AC	2,663 ms 9,812 KB
testcase_56	AC	2,650 ms 9,824 KB
testcase_57	TLE	-
testcase_58	--	-
testcase_59	--	-

権限があれば一括ダウンロードができます

ソースコード

raw source code

#line 1 "code.cpp"
#pragma GCC optimize("Ofast")
#pragma GCC target("avx")
#pragma GCC optimize("unroll-loops")
#line 2 "library/template/template.hpp"
#include<bits/stdc++.h>
#line 3 "library/template/macro.hpp"

#define SELECT4(a,b,c,d,e,...) e
#define SELECT3(a,b,c,d,...) d
#define REP1(a) for(ll i=0;i<(ll)(a);++i)
#define REP2(i,a) for(ll i=0;i<(ll)(a);++i)
#define REP3(i,a,b) for(ll i=(ll)(a);i<(ll)(b);++i)
#define REP4(i,a,b,c) for(ll i=(ll)(a);i<(ll)(b);i+=(ll)(c))
#define rep(...) SELECT4(__VA_ARGS__,REP4,REP3,REP2,REP1)(__VA_ARGS__)
#define RREP1(a) for(ll i=(ll)(a)-1;i>=0;--i)
#define RREP2(i,a) for(ll i=(ll)(a)-1;i>=0;--i)
#define RREP3(i,a,b) for(ll i=(ll)(b)-1;i>=(ll)(a);--i)
#define rrep(...) SELECT3(__VA_ARGS__,RREP3,RREP2,RREP1)(__VA_ARGS__)
#define all(v) std::begin(v),std::end(v)
#define rall(v) std::rbegin(v),std::rend(v)
#define INT(...) int __VA_ARGS__;scan(__VA_ARGS__)
#define LL(...) ll __VA_ARGS__;scan(__VA_ARGS__)
#define STR(...) string __VA_ARGS__;scan(__VA_ARGS__)
#define CHR(...) char __VA_ARGS__;scan(__VA_ARGS__)
#define DBL(...) double __VA_ARGS__;scan(__VA_ARGS__)
#define LD(...) ld __VA_ARGS__;scan(__VA_ARGS__)
#define pb push_back
#define eb emplace_back
#line 3 "library/template/alias.hpp"

using ll=long long;
using ull=unsigned long long;
using ld=long double;
using pi=std::pair<int,int>;
using pl=std::pair<ll,ll>;
using vi=std::vector<int>;
using vl=std::vector<ll>;
using vs=std::vector<std::string>;
using vc=std::vector<char>;
using vvl=std::vector<vl>;
using vd=std::vector<double>;
using vp=std::vector<pl>;
using vb=std::vector<bool>;
template<typename T>
struct infinity{
  static constexpr T max=std::numeric_limits<T>::max();
  static constexpr T min=std::numeric_limits<T>::min();
  static constexpr T value=std::numeric_limits<T>::max()/2;
  static constexpr T mvalue=std::numeric_limits<T>::min()/2;
};
template<typename T>constexpr T INF=infinity<T>::value;
constexpr ll inf=INF<ll>;
constexpr ld EPS=1e-8;
constexpr ld PI=3.1415926535897932384626;
constexpr int dx[8]={1,0,-1,0,1,-1,-1,1};
constexpr int dy[8]={0,1,0,-1,1,1,-1,-1};
#line 5 "library/template/func.hpp"

inline constexpr int msb(ull x){
  int res=x?0:-1;
  if(x&0xffffffff00000000)x&=0xffffffff00000000,res+=32;
  if(x&0xffff0000ffff0000)x&=0xffff0000ffff0000,res+=16;
  if(x&0xff00ff00ff00ff00)x&=0xff00ff00ff00ff00,res+=8;
  if(x&0xf0f0f0f0f0f0f0f0)x&=0xf0f0f0f0f0f0f0f0,res+=4;
  if(x&0xcccccccccccccccc)x&=0xcccccccccccccccc,res+=2;
  return res+(x&0xaaaaaaaaaaaaaaaa?1:0);
}
inline constexpr int ceil_log2(ull x){return x?msb(x-1)+1:0;}
inline constexpr ull reverse(ull x){
  x=((x&0x5555555555555555)<<1)|((x&0xaaaaaaaaaaaaaaaa)>>1);
  x=((x&0x3333333333333333)<<2)|((x&0xcccccccccccccccc)>>2);
  x=((x&0x0f0f0f0f0f0f0f0f)<<4)|((x&0xf0f0f0f0f0f0f0f0)>>4);
  x=((x&0x00ff00ff00ff00ff)<<8)|((x&0xff00ff00ff00ff00)>>8);
  
  x=((x&0x0000ffff0000ffff)<<16)|((x&0xffff0000ffff0000)>>16);
  return (x<<32)|(x>>32);
}
inline constexpr ull reverse(ull x,int len){return reverse(x)>>(64-len);}
inline constexpr int popcnt(ull x){
#if __cplusplus>=202002L
  return std::popcount(x);
#endif
  x=(x&0x5555555555555555)+((x>>1)&0x5555555555555555);
  x=(x&0x3333333333333333)+((x>>2)&0x3333333333333333);
  x=(x&0x0f0f0f0f0f0f0f0f)+((x>>4)&0x0f0f0f0f0f0f0f0f);
  x=(x&0x00ff00ff00ff00ff)+((x>>8)&0x00ff00ff00ff00ff);
  x=(x&0x0000ffff0000ffff)+((x>>16)&0x0000ffff0000ffff);
  return (x&0x00000000ffffffff)+((x>>32)&0x00000000ffffffff);
}
template<typename T,typename U>
inline constexpr bool chmin(T&a,U b){return a>b&&(a=b,true);}
template<typename T,typename U>
inline constexpr bool chmax(T&a,U b){return a<b&&(a=b,true);}
inline constexpr ll gcd(ll a,ll b){
  if(a<0)a=-a;
  if(b<0)b=-b;
  while(b){
    const ll c=b;
    b=a%b;
    a=c;
  }
  return a;
}
inline constexpr ll lcm(ll a,ll b){return a/gcd(a,b)*b;}
inline constexpr bool is_prime(ll n){
  if(n<=1)return false;
  for(ll i=2;i*i<=n;i++){
    if(n%i==0)return false;
  }
  return true;
}
inline constexpr ll my_pow(ll a,ll b){
  ll res=1;
  while(b){
    if(b&1)res*=a;
    a*=a;
    b>>=1;
  }
  return res;
}
inline constexpr ll mod_pow(ll a,ll b,const ll&mod){
  if(mod==1)return 0;
  a%=mod;
  ll res=1;
  while(b){
    if(b&1)(res*=a)%=mod;
    (a*=a)%=mod;
    b>>=1;
  }
  return res;
}
inline ll mod_inv(ll a,const ll&mod){
  ll b=mod,x=1,u=0,t;
  while(b){
    t=a/b;
    std::swap(a-=t*b,b);
    std::swap(x-=t*u,u);
  }
  if(x<0)x+=mod;
  return x;
}
template<typename T,typename U>
std::ostream &operator<<(std::ostream&os,const std::pair<T,U>&p){os<<p.first<<" "<<p.second;return os;}
template<typename T,typename U>
std::istream &operator>>(std::istream&is,std::pair<T,U>&p){is>>p.first>>p.second;return is;}
template<typename T>
std::ostream &operator<<(std::ostream&os,const std::vector<T>&v){for(auto it=std::begin(v);it!=std::end(v);){os<<*it<<((++it)!=std::end(v)?" ":"");}return os;}
template<typename T>
std::istream &operator>>(std::istream&is,std::vector<T>&v){for(T &in:v){is>>in;}return is;}
inline void scan(){}
template<class Head,class... Tail>
inline void scan(Head&head,Tail&... tail){std::cin>>head;scan(tail...);}
template<class T>
inline void print(const T &t){std::cout<<t<<'\n';}
template<class Head, class... Tail>
inline void print(const Head &head, const Tail &... tail){std::cout<<head<<' ';print(tail...);}
template<class... T>
inline void fin(const T &... a){print(a...);exit(0);}
#line 5 "library/template/util.hpp"

struct IOSetup{
  IOSetup(){
    std::cin.tie(nullptr);
    std::ios::sync_with_stdio(false);
    std::cout.tie(0);
    std::cout<<std::fixed<<std::setprecision(12);
    std::cerr<<std::fixed<<std::setprecision(12);
  }
};
template<typename F>
struct REC{
  private:
  F f;
  public:
  explicit constexpr REC(F&&f_):f(std::forward<F>(f_)){}
  template<typename... Args>
  constexpr auto operator()(Args&&...args)const{
    return f(*this, std::forward<Args>(args)...);
  }
};
template<typename T,typename Comp=std::less<T>>
struct compressor{
  private:
  std::vector<T>data;
  Comp cmp;
  bool sorted=false;
  public:
  compressor():compressor(Comp()){}
  compressor(const Comp&cmp):cmp(cmp){}
  compressor(const std::vector<T>&dat,const Comp&cmp=Comp()):data(dat),cmp(cmp){}
  compressor(std::vector<T>&&dat,const Comp&cmp=Comp()):data(std::move(dat)),cmp(cmp){}
  compressor(std::initializer_list<T>li,const Comp&cmp=Comp()):data(li.begin(),li.end()),cmp(cmp){}
  void push_back(const T&v){assert(!sorted);data.push_back(v);}
  void push_back(T&&v){assert(!sorted);data.push_back(std::move(v));}
  template<typename... Args>void emplace_back(Args&&...args){assert(!sorted);data.emplace_back(std::forward<Args>(args)...);}
  void push(const std::vector<T>&v){
    assert(!sorted);
    const int n=data.size();
    data.resize(v.size()+n);
    for(int i=0;i<(int)v.size();i++)data[i+n]=v[i];
  }
  void build(){
    assert(!sorted);sorted=1;
    std::sort(data.begin(),data.end(),cmp);
    data.erase(unique(data.begin(),data.end(),[&](const T&l,const T&r)->bool {return !cmp(l,r)&&!cmp(r,l);}),data.end());
  }
  const T&operator[](int k)const& {
    assert(sorted);
    return data[k];
  }
  int get_index(const T&v)const {
    assert(sorted);
    return int(lower_bound(data.begin(),data.end(),v,cmp)-data.begin());
  }
  void press(std::vector<T>&v)const {
    assert(sorted);
    for(auto&&i:v)i=get_index(i);
  }
  std::vector<int>pressed(const std::vector<T>&v)const {
    assert(sorted);
    std::vector<int>ret(v.size());
    for(int i=0;i<(int)v.size();i++)ret[i]=get_index(v[i]);
    return ret;
  }
  int size()const {
    assert(sorted);
    return data.size();
  }
};
#line 4 "library/template/debug.hpp"

template<typename T,typename=void>
struct is_specialize:std::false_type{};
template<typename T>
struct is_specialize<T,typename std::conditional<false,typename T::iterator, void>::type>:std::true_type{};
template<typename T>
struct is_specialize<T,typename std::conditional<false,decltype(T::first),void>::type>:std::true_type{};
template<typename T>
struct is_specialize<T,std::enable_if_t<std::is_integral<T>::value,void>>:std::true_type{};
inline void dump(const char&t){std::cerr<<t;}
inline void dump(const std::string&t){std::cerr<<t;}
inline void dump(const bool&t){std::cerr<<(t?"true":"false");}
template <typename T,std::enable_if_t<!is_specialize<T>::value,std::nullptr_t> =nullptr>
inline void dump(const T&t){std::cerr<<t;}
template<typename T>
inline void dump(const T&t,std::enable_if_t<std::is_integral<T>::value>* =nullptr){std::string tmp;if(t==infinity<T>::value||t==infinity<T>::max)tmp="inf";if(std::is_signed<T>::value&&(t==infinity<T>::mvalue||t==infinity<T>::min))tmp="-inf";if(tmp.empty())tmp=std::to_string(t);std::cerr<<tmp;}
template<typename T,typename U>
inline void dump(const std::pair<T,U>&);
template<typename T>
inline void dump(const T&t,std::enable_if_t<!std::is_void<typename T::iterator>::value>* =nullptr){std::cerr<<"{";for(auto it=std::begin(t);it!=std::end(t);){dump(*it);std::cerr<<(++it==t.end()?"":",");}std::cerr<<"}";}
template<typename T,typename U>
inline void dump(const std::pair<T,U>&t){std::cerr<<"(";dump(t.first);std::cerr<<",";dump(t.second);std::cerr<<")";}
inline void trace(){std::cerr<<std::endl;}
template<typename Head,typename... Tail>
inline void trace(Head&&head,Tail&&... tail){dump(head);if(sizeof...(tail))std::cerr<<",";trace(std::forward<Tail>(tail)...);}
#ifdef ONLINE_JUDGE
#define debug(...) (void(0))
#else
#define debug(...) do{std::cerr<<#__VA_ARGS__<<"=";trace(__VA_ARGS__);}while(0)
#endif
#line 4 "library/template/type-traits.hpp"

template<std::size_t size>
struct int_least{
  static_assert(size<=128,"size must be less than or equal to 128");
  using type=typename std::conditional<
    size<=8,std::int_least8_t,
    typename std::conditional<
      size<=16,std::int_least16_t,
      typename std::conditional<
        size<=32,std::int_least32_t,
        typename std::conditional<size<=64,std::int_least64_t,__int128_t>::type>::type>::type>::type;
};
template<std::size_t size>using int_least_t=typename int_least<size>::type;
template<std::size_t size>
struct uint_least{
  static_assert(size<=128,"size must be less than or equal to 128");
  using type=typename std::conditional<
    size<=8,std::uint_least8_t,
    typename std::conditional<
      size<=16,std::uint_least16_t,
      typename std::conditional<
        size<=32,std::uint_least32_t,
        typename std::conditional<size<=64,std::uint_least64_t,__uint128_t>::type>::type>::type>::type;
};
template<std::size_t size>using uint_least_t=typename uint_least<size>::type;
template<typename T>
using double_size_int=int_least<std::numeric_limits<T>::digits*2+1>;
template<typename T>using double_size_int_t=typename double_size_int<T>::type;
template<typename T>
using double_size_uint=uint_least<std::numeric_limits<T>::digits*2>;
template<typename T>using double_size_uint_t=typename double_size_uint<T>::type;
template<typename T>
using double_size=typename std::conditional<std::is_signed<T>::value,double_size_int<T>,double_size_uint<T>>::type;
template<typename T>using double_size_t=typename double_size<T>::type;
#line 9 "library/template/template.hpp"
using namespace std;
#line 3 "bigint.hpp"
#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;
}
#line 6 "code.cpp"
typedef string::const_iterator State;
bigint expression(State&st);
bigint term(State&st);
bigint factor(State&st);
bigint number(State&st);
bigint expression(State&st){
    vector<bigint>f={term(st)};
    while(*st=='+'||*st=='-'){
        if(*st=='+'){
            st++;
            f.pb(term(st));
        }else{
            st++;
            f.pb(-term(st));
        }
    }
    if(f.size()==1)return f[0];
    priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>pq;
    rep(i,f.size()){
        pq.emplace(f[i].a.size(),i);
    }
    while(pq.size()>1){
        auto a=pq.top();pq.pop();
        auto b=pq.top();pq.pop();
        f[a.second]+=f[b.second];
        pq.emplace(f[a.second].a.size(),a.second);
    }
    return f[pq.top().second];
}
bigint term(State&st){
    vector<bigint>f={factor(st)};
    while(*st=='*'){
        st++;
        f.emplace_back(factor(st));
    }
    if(f.size()==1)return f[0];
    priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>pq;
    rep(i,f.size()){
        pq.emplace(f[i].a.size(),i);
    }
    while(pq.size()>1){
        auto a=pq.top();pq.pop();
        auto b=pq.top();pq.pop();
        f[a.second]*=f[b.second];
        pq.emplace(f[a.second].a.size(),a.second);
    }
    return f[pq.top().second];
}
bigint factor(State&st){
    if(*st=='('){
        st++;
        bigint tmp=expression(st);
        assert(*st==')');
        st++;
        return tmp;
    }
    return number(st);
}
bigint number(State&st){
    if(*st=='-'){
        st++;
        return -number(st);
    }
    string t="";
    while(isdigit(*st)){
        t+=*st;
        st++;
    }
    return bigint(t);
}
int main(){
    IOSetup();
    LL(n);
    STR(s);
    State it=s.begin();
    bigint ans=expression(it);
    cout<<ans<<endl;
}

yukicoder

結果

テストケース

ソースコード