#939889 (C++17) No.2595 Parsing Challenge

• 問題: No.2595 Parsing Challenge
• ユーザー: tko919
• 提出日時: 2023-12-23 01:19:20
• 言語: C++17 (gcc 13.3.0 + boost 1.87.0)
• 結果: TLE
• 実行時間: -
• コード長: 19,008 bytes
• コンパイル時間: 3,782 ms
• コンパイル使用メモリ: 236,180 KB
• 最終ジャッジ日時: 2025-02-18 13:28:46
• ジャッジサーバーID （参考情報）: judge2 / judge2

ファイルパターン	結果
sample	AC * 5
other	AC * 25 TLE * 1 -- * 29

ソースコード

#line 1 "library/Template/template.hpp"
#include <bits/stdc++.h>
using namespace std;

#define rep(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define ALL(v) (v).begin(),(v).end()
#define UNIQUE(v) sort(ALL(v)),(v).erase(unique(ALL(v)),(v).end())
#define SZ(v) (int)v.size()
#define MIN(v) *min_element(ALL(v))
#define MAX(v) *max_element(ALL(v))
#define LB(v,x) int(lower_bound(ALL(v),(x))-(v).begin())
#define UB(v,x) int(upper_bound(ALL(v),(x))-(v).begin())

using ll=long long int;
using ull=unsigned long long;
const int inf = 0x3fffffff;
const ll INF = 0x1fffffffffffffff;

template<typename T>inline bool chmax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
template<typename T>inline bool chmin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
template<typename T,typename U>T ceil(T x,U y){assert(y!=0); if(y<0)x=-x,y=-y; return (x>0?(x+y-1)/y:x/y);}
template<typename T,typename U>T floor(T x,U y){assert(y!=0); if(y<0)x=-x,y=-y; return (x>0?x/y:(x-y+1)/y);}
template<typename T>int popcnt(T x){return __builtin_popcountll(x);}
template<typename T>int topbit(T x){return (x==0?-1:63-__builtin_clzll(x));}
template<typename T>int lowbit(T x){return (x==0?-1:__builtin_ctzll(x));}
#line 2 "library/Utility/fastio.hpp"
#include <unistd.h>

class FastIO{
    static constexpr int L=1<<16;
    char rdbuf[L];
    int rdLeft=0,rdRight=0;
    inline void reload(){
        int len=rdRight-rdLeft;
        memmove(rdbuf,rdbuf+rdLeft,len);
        rdLeft=0,rdRight=len;
        rdRight+=fread(rdbuf+len,1,L-len,stdin);
    }
    inline bool skip(){
        for(;;){
            while(rdLeft!=rdRight and rdbuf[rdLeft]<=' ')rdLeft++;
            if(rdLeft==rdRight){
                reload();
                if(rdLeft==rdRight)return false;
            }
            else break;
        }
        return true;
    }
    template<typename T,enable_if_t<is_integral<T>::value,int> =0>inline bool _read(T& x){
        if(!skip())return false;
        if(rdLeft+20>=rdRight)reload();
        bool neg=false;
        if(rdbuf[rdLeft]=='-'){
            neg=true;
            rdLeft++;
        }
        x=0;
        while(rdbuf[rdLeft]>='0' and rdLeft<rdRight){
            x=x*10+(neg?-(rdbuf[rdLeft++]^48):(rdbuf[rdLeft++]^48));
        }
        return true;
    }
    inline bool _read(__int128_t& x){
        if(!skip())return false;
        if(rdLeft+40>=rdRight)reload();
        bool neg=false;
        if(rdbuf[rdLeft]=='-'){
            neg=true;
            rdLeft++;
        }
        x=0;
        while(rdbuf[rdLeft]>='0' and rdLeft<rdRight){
            x=x*10+(neg?-(rdbuf[rdLeft++]^48):(rdbuf[rdLeft++]^48));
        }
        return true;
    }
    inline bool _read(__uint128_t& x){
        if(!skip())return false;
        if(rdLeft+40>=rdRight)reload();
        x=0;
        while(rdbuf[rdLeft]>='0' and rdLeft<rdRight){
            x=x*10+(rdbuf[rdLeft++]^48);
        }
        return true;
    }
    template<typename T,enable_if_t<is_floating_point<T>::value,int> =0>inline bool _read(T& x){
        if(!skip())return false;
        if(rdLeft+20>=rdRight)reload();
        bool neg=false;
        if(rdbuf[rdLeft]=='-'){
            neg=true;
            rdLeft++;
        }
        x=0;
        while(rdbuf[rdLeft]>='0' and rdbuf[rdLeft]<='9' and rdLeft<rdRight){
            x=x*10+(rdbuf[rdLeft++]^48);
        }
        if(rdbuf[rdLeft]!='.')return true;
        rdLeft++;
        T base=.1;
        while(rdbuf[rdLeft]>='0' and rdbuf[rdLeft]<='9' and rdLeft<rdRight){
            x+=base*(rdbuf[rdLeft++]^48);
            base*=.1;
        }
        if(neg)x=-x;
        return true;
    }
    inline bool _read(char& x){
        if(!skip())return false;
        if(rdLeft+1>=rdRight)reload();
        x=rdbuf[rdLeft++];
        return true;
    }
    inline bool _read(string& x){
        if(!skip())return false;
        for(;;){
            int pos=rdLeft;
            while(pos<rdRight and rdbuf[pos]>' ')pos++;
            x.append(rdbuf+rdLeft,pos-rdLeft);
            if(rdLeft==pos)break;
            rdLeft=pos;
            if(rdLeft==rdRight)reload();
            else break;
        }
        return true;
    }
    template<typename T>inline bool _read(vector<T>& v){
        for(auto& x:v){
            if(!_read(x))return false;
        }
        return true;
    }

    char wtbuf[L],tmp[50];
    int wtRight=0;
    inline void _write(const char& x){
        if(wtRight>L-32)flush();
        wtbuf[wtRight++]=x;
    }
    inline void _write(const string& x){
        for(auto& c:x)_write(c);
    }
    template<typename T,enable_if_t<is_integral<T>::value,int> =0>inline void _write(T x){
        if(wtRight>L-32)flush();
        if(x==0){
            _write('0');
            return;
        }
        else if(x<0){
            _write('-');
            if (__builtin_expect(x == std::numeric_limits<T>::min(), 0)) {
                switch (sizeof(x)) {
                case 2: _write("32768"); return;
                case 4: _write("2147483648"); return;
                case 8: _write("9223372036854775808"); return;
                }
            }
            x=-x;
        }
        int pos=0;
        while(x!=0){
            tmp[pos++]=char((x%10)|48);
            x/=10;
        }
        rep(i,0,pos)wtbuf[wtRight+i]=tmp[pos-1-i];
        wtRight+=pos;
    }
    inline void _write(__int128_t x){
        if(wtRight>L-40)flush();
        if(x==0){
            _write('0');
            return;
        }
        else if(x<0){
            _write('-');
            x=-x;
        }
        int pos=0;
        while(x!=0){
            tmp[pos++]=char((x%10)|48);
            x/=10;
        }
        rep(i,0,pos)wtbuf[wtRight+i]=tmp[pos-1-i];
        wtRight+=pos;
    }
    inline void _write(__uint128_t x){
        if(wtRight>L-40)flush();
        if(x==0){
            _write('0');
            return;
        }
        int pos=0;
        while(x!=0){
            tmp[pos++]=char((x%10)|48);
            x/=10;
        }
        rep(i,0,pos)wtbuf[wtRight+i]=tmp[pos-1-i];
        wtRight+=pos;
    }
    inline void _write(double x){
        ostringstream oss;
        oss << fixed << setprecision(15) << double(x);
        string s = oss.str();
        _write(s);
    }
    template<typename T>inline void _write(const vector<T>& v){
        rep(i,0,v.size()){
            if(i)_write(' ');
            _write(v[i]);
        }
    }
public:
    FastIO(){}
    ~FastIO(){flush();}
    inline void read(){}
    template <typename Head, typename... Tail>inline void read(Head& head,Tail&... tail){
        assert(_read(head));
        read(tail...); 
    }
    template<bool ln=true,bool space=false>inline void write(){if(ln)_write('\n');}
    template <bool ln=true,bool space=false,typename Head, typename... Tail>inline void write(const Head& head,const Tail&... tail){
        _write(head);
        write<ln,true>(tail...); 
        if(space)_write(' ');
    }
    inline void flush(){
        fwrite(wtbuf,1,wtRight,stdout);
        wtRight=0;
    }
};

/**
 * @brief Fast IO
 */
#line 3 "sol.cpp"

#line 2 "library/Convolution/fft.hpp"

namespace FFT{
    struct C{
        double x,y;
        C(double _x=0,double _y=0):x(_x),y(_y){}
        C operator~()const{return C(x,-y);}
        C operator*(const C& c)const{return C(x*c.x-y*c.y,x*c.y+y*c.x);}
        C operator+(const C& c)const{return C(x+c.x,y+c.y);}
        C operator-(const C& c)const{return C(x-c.x,y-c.y);}
    };
    vector<vector<C>> w(1,vector<C>(1,1));
    void init(int lg){
        for(int d=1,m=1;d<=lg;d++,m<<=1)if(d>=(int)w.size()){
             w.emplace_back(m);
             const double th=M_PI/m;
             for(int i=0;i<m;i++)w[d][i]=(i&1?C(cos(th*i),sin(th*i)):w[d-1][i>>1]);
        }
    }
    void fft(vector<C>& f,bool inv){
        const int n=f.size(); const int lg=__lg(n);
        if(lg>=(int)w.size())init(lg);
        if(inv){
            for(int k=1;k<=lg;k++){
                const int d=1<<(k-1);
                for(int s=0;s<n;s+=2*d){
                    for(int i=s;i<s+d;i++){
                        C x=f[i],y=~w[k][i-s]*f[d+i];
                        f[i]=x+y; f[d+i]=x-y;
                    }
                }
            }
         }
         else{
             for(int k=lg;k;k--){
                 const int d=1<<(k-1);
                 for(int s=0;s<n;s+=2*d){
                     for(int i=s;i<s+d;i++){
                         C x=f[i],y=f[d+i];
                         f[i]=x+y; f[d+i]=w[k][i-s]*(x-y);
                     }
                 }
             }
         }
    }
    template<typename T>vector<T> mult(const vector<T>& a,const vector<T>& b){
        const int as=a.size(); const int bs=b.size(); 
        if(!as or !bs)return {};
        const int cs=as+bs-1; vector<T> c(cs);
        if(max(as,bs)<16){
            for(int i=0;i<as;i++)for(int j=0;j<bs;j++){
                c[i+j]+=(int)a[i]*b[j];
            }
            return c;
        }
        const int n=1<<__lg(2*cs-1); vector<C> f(n);
        for(int i=0;i<as;i++)f[i].x=a[i];
        for(int i=0;i<bs;i++)f[i].y=b[i];
        fft(f,0); static const C rad(0,-.25);
        for(int i=0;i<n;i++){
            int j=i?i^((1<<__lg(i))-1):0;
            if(i>j)continue;
            C x=f[i]+~f[j],y=f[i]-~f[j];
            f[i]=x*y*rad; f[j]=~f[i];
        }
        fft(f,1); for(int i=0;i<cs;i++)c[i]=round(f[i].x/n);
        return c;
    }
    template<typename T>vector<T> square(const vector<T>& a){
        const int as=a.size(); if(!as)return {};
        const int cs=as*2-1; vector<T> c(cs);
        if(as<16){
            for(int i=0;i<as;i++)for(int j=0;j<as;j++){
                c[i+j]+=(int)a[i]*a[j];
            }
            return c;
        }
        const int n=1<<__lg(cs*2-1); vector<C> f(n);
        for(int i=0;i<as;i++)f[i].x=a[i];
        fft(f,0); for(int i=0;i<n;i++)f[i]=f[i]*f[i];
        fft(f,1); for(int i=0;i<cs;i++)c[i]=round(f[i].x/n);
        return c;
    }
}

/**
 * @brief Fast Fourier Transform
 */
#line 3 "library/Math/bigint.hpp"

template<int D>struct bigint{
   static const int B=pow(10,D);
   int sign=0; vector<ll> v;
   static int get_D(){return D;}
   static int get_B(){return B;}
   bigint(ll x=0){
      if(x<0)x*=-1,sign=1;
      while(x){v.push_back(x%B); x/=B;}
   }
   bigint(string s){
      if(s[0]=='-')s.erase(s.begin()),sign=1;
      int add=0,cnt=0,base=1;
      while(s.size()){
         if(cnt==D){
            v.push_back(add);
            cnt=0; add=0; base=1;
         }
         add=(s.back()-'0')*base+add;
         cnt++; base*=10; s.pop_back();
      } if(add)v.push_back(add);
   }
   bigint operator-()const{bigint res=*this; res.sign^=1;return res;}
   bigint abs()const{bigint res=*this; res.sign=0; return res;}
   ll& operator[](const int i){return v[i];}
   int size()const{return v.size();}
   void norm(){
      rep(i,0,v.size()-1){
         if(v[i]>=0){v[i+1]+=v[i]/B; v[i]%=B;}
         else{int c=(-v[i]+B-1)/B; v[i]+=c*B; v[i+1]-=c;}
      }
      while(!v.empty() and v.back()>=B){
         int c=v.back()/B;
         v.back()%=B; v.push_back(c);
      }
      while(!v.empty() and v.back()==0)v.pop_back();
   }
   string to_str()const{
      string res;
      if(v.empty())return "0";
      if(sign)res+='-';
      res+=to_string(v.back());
      for(int i=v.size()-2;i>=0;i--){
         string add; int w=v[i];
         rep(_,0,D){
            add+=('0'+(w%10)); w/=10;
         } reverse(ALL(add)); res+=add;
      } return res;
   }
   friend istream& operator>>(istream& is,bigint<D>& x){
      string tmp; is>>tmp; x=bigint(tmp); return is;
   }
   friend ostream& operator<<(ostream& os,bigint<D> x){
      os<<x.to_str(); return os;
   }
   bigint& operator<<=(const int& x){
      if(!v.empty()){
         vector<ll> add(x,0);
         v.insert(v.begin(),ALL(add));
      } return *this;
   }
   bigint& operator>>=(const int& x){
      v=vector<ll>(v.begin()+min(x,(int)v.size()),v.end());
      return *this;
   }
   bigint& operator+=(const bigint& x){
      if(sign!=x.sign){*this-=(-x); return *this;}
      if((int)v.size()<(int)x.size())v.resize(x.size(),0);
      rep(i,0,x.size()){v[i]+=x.v[i];} norm(); return *this;
   }
   bigint& operator-=(const bigint& x){
      if(sign!=x.sign){*this+=(-x); return *this;}
      if(abs()<x.abs()){*this=x-(*this); sign^=1; return *this;}
      rep(i,0,x.size()){v[i]-=x.v[i];} norm(); return *this;
   }
   bigint& operator*=(const bigint& x){
      sign^=x.sign;
      auto v1=FFT::mult(v,x.v);
      v.assign(v1.size(),0);
      rep(i,0,v1.size()){
         ll val=v1[i];
         for(int j=i;val;j++){
            if(j==(int)v.size())v.push_back(0);
            v[j]+=val%B; val/=B;
         }
      } norm(); return *this;
   }
   bigint& operator/=(const bigint& x){  
      bigint a=abs(),b=x.abs(); sign^=x.sign;
      if(a<b)return *this=bigint();
      if(b==bigint(1))return *this=a;
      int d=a.size()-b.size()+1;
      bigint inv(1LL*B*B/b.v.back()),pre;
      int cur=2,bcur=1; pre=bigint(0);
      while(inv!=pre or bcur<b.size()){
         bcur=min(bcur<<1,b.size());
         bigint c; c.v=vector<ll>(b.v.end()-bcur,b.v.end());
         pre=inv; inv*=((bigint(2)<<(cur+bcur-1))-inv*c);
         cur=min(cur<<1,d);
         inv.v=vector<ll>(inv.v.end()-cur,inv.v.end());
      }
      inv.v=vector<ll>(inv.v.end()-d,inv.v.end());
      bigint res=a*inv; res>>=(a.size());
      bigint mul=res*b;
      while(mul+b<=a){res+=bigint(1); mul+=b;}
      v=res.v; return *this;
   }
   bigint& operator%=(const bigint& x){
      bigint div=(*this)/x; (*this)-=div*x; return *this;
   }
   bigint square(){
      bigint res=*this; res.sign=0;
      auto v1=FFT::mult(v,v);
      res.v.assign(v1.size(),0);
      rep(i,0,v1.size()){
         ll val=v1[i];
         for(int j=i;val;j++){
            if(j==(int)res.v.size())res.v.push_back(0);
            res.v[j]+=val%B; val/=B;
         }
      } res.norm(); return res;
   }
   bigint mul(ll x){
      bigint res=*this; if(x<0)res.sign^=1,x*=-1;
      for(int i=res.v.size()-1;i>=0;i--)res.v[i]*=x;
      res.norm(); return res;
   }
   bigint div(ll x){
      bigint res=*this; if(x<0)res.sign^=1,x*=-1;
      for(int i=res.v.size()-1;i>=0;i--){
         if(res.v[i]%x!=0 and i!=0){res.v[i-1]+=B*(res.v[i]%x);} res.v[i]/=x;
      } res.norm(); return res;
   }
   bigint operator<<(const int& x)const{return bigint(*this)<<=x;}
   bigint operator>>(const int& x)const{return bigint(*this)>>=x;}
   bigint operator+(const bigint& x)const{return bigint(*this)+=x;}
   bigint operator-(const bigint& x)const{return bigint(*this)-=x;}
   bigint operator*(const bigint& x)const{return bigint(*this)*=x;}
   bigint operator/(const bigint& x)const{return bigint(*this)/=x;}
   bigint operator%(const bigint& x)const{return bigint(*this)%=x;}
   bool operator<(const bigint& x)const{
      if(sign!=x.sign)return sign>x.sign;
      if((int)v.size()!=(int)x.size()){
         if(sign)return (int)x.size()<(int)v.size();
         else return (int)v.size()<(int)x.size();
      }
      for(int i=v.size()-1;i>=0;i--)if(v[i]!=x.v[i]){
         if(sign)return x.v[i]<v[i];
         else return v[i]<x.v[i];
      }
      return false;
   }
   bool operator>(const bigint& x)const{return x<*this;}
   bool operator<=(const bigint& x)const{return !(*this>x);}
   bool operator>=(const bigint& x)const{return !(*this<x);}
   bool operator==(const bigint& x)const{return !(*this<x) and !(*this>x);}
   bool operator!=(const bigint& x)const{return !(*this==x);}
};
typedef bigint<4> Bigint;
 
struct Bigfloat{
   Bigint v; int p=0;
   Bigfloat(){}
   Bigfloat(const ll& _v){v=Bigint(_v);}
   Bigfloat(const Bigint& _v,int _p=0):v(_v),p(_p){}
   void set(int _p){if(p<_p){v>>=(_p-p);} else{v<<=(p-_p);} p=_p;}
   Bigint to_int()const{if(p<0)return v>>(-p); else return v<<p;}
   Bigfloat& operator+=(const Bigfloat& x){
      if(p>x.p)set(x.p),v+=x.v;
      else v+=x.v<<(x.p-p);
      return *this;
   }
   Bigfloat& operator-=(const Bigfloat& x){
      if(p>x.p)set(x.p),v-=x.v;
      else v-=x.v<<(x.p-p);
      return *this;
   }
   Bigfloat square(){Bigfloat res=*this; res.p*=2; res.v=res.v.square(); return res;}
   Bigfloat mul(ll x){Bigfloat res=*this; res.v=v.mul(x); return res;}
   Bigfloat div(ll x){Bigfloat res=*this; res.v=v.div(x); return res;}
   Bigfloat& operator*=(const Bigfloat& x){p+=x.p; v*=x.v; return *this;}
   Bigfloat& operator/=(const Bigfloat& x){p-=x.p; v/=x.v; return *this;}
   Bigfloat operator+(const Bigfloat& x)const{return Bigfloat(*this)+=x;}
   Bigfloat operator-(const Bigfloat& x)const{return Bigfloat(*this)-=x;}
   Bigfloat operator*(const Bigfloat& x)const{return Bigfloat(*this)*=x;}
   Bigfloat operator/(const Bigfloat& x)const{return Bigfloat(*this)/=x;}
   string to_str(){
      string res=v.abs().to_str(); int d=Bigint::get_D();
      if(p*d>0)res+=string(p*d,'0');
      else if(-p*d>=1 and -p*d<(int)res.size()){
         res=res.substr(0,(int)res.size()+p*d)+'.'+res.substr((int)res.size()+p*d);
      }
      else if(-p*d>=(int)res.size())res="0."+string(-p*d-(int)res.size(),'0')+res;
      if(v.sign){res.insert(res.begin(),'-');} return res;
   }
   friend ostream& operator<<(ostream& os,Bigfloat x){
      os<<x.to_str(); return os;
   }
};
 
Bigfloat sqrt(ll n,int d){
   Bigfloat res(Bigint((ll)sqrt(1LL*Bigint::get_B()*Bigint::get_B()/n)),-1),pre;
   int cur=1;
   while(pre.v!=res.v){
      cur=min(cur<<1,d);
      pre=res; Bigfloat add=Bigfloat(1)-res.square().mul(n);
      add.set(-cur); res+=(res*add).div(2); res.set(-cur);
   } return res.mul(n);
}

/**
 * @brief Big Integer(Float)
 */
#line 5 "sol.cpp"

typedef string::const_iterator State;

Bigint expr(State &beg);
Bigint term(State &beg);
Bigint factor(State &beg);
Bigint num(State &beg);

Bigint expr(State &beg) {
    auto ret = term(beg);
    for (;;) {
        if ((*beg) == '+') {
            beg++;
            ret += term(beg);
        } else if ((*beg) == '-') {
            beg++;
            ret -= term(beg);
        } else
            break;
    }
    return ret;
}

Bigint term(State &beg) {
    deque<Bigint> deq;
    deq.push_back(factor(beg));
    while ((*beg) == '*') {
        beg++;
        deq.push_back(factor(beg));
    }
    while (deq.size() > 1) {
        auto x = deq[0];
        deq.pop_front();
        auto y = deq[0];
        deq.pop_front();
        deq.push_back(x * y);
    }
    return deq[0];
}

Bigint factor(State &beg) {
    if ((*beg) == '(') {
        beg++;
        auto ret = expr(beg);
        beg++;
        return ret;
    } else
        return num(beg);
}

Bigint num(State &beg) {
    Bigint ret;
    bool neg = 0;
    while ((*beg) == '-') {
        neg ^= 1;
        beg++;
    }
    while (isdigit(*beg)) {
        ret *= 10;
        ret += int((*beg) - '0');
        beg++;
    }
    if (neg)
        ret = -ret;
    return ret;
}

FastIO io;
int main() {
    int n;
    string s;
    io.read(n, s);

    State it = s.begin();
    auto ret = expr(it);
    io.write(ret.to_str());
    return 0;
}