#772188 (C++17) No.265 数学のテスト

提出ソース

結果

問題	No.265 数学のテスト
ユーザー	re_re0101
提出日時	2022-06-18 01:21:37
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	110 ms / 2,000 ms
コード長	11,840 bytes
コンパイル時間	4,967 ms
コンパイル使用メモリ	273,732 KB
実行使用メモリ	5,248 KB
最終ジャッジ日時	2024-10-09 11:56:24
合計ジャッジ時間	6,269 ms
ジャッジサーバーID （参考情報）	judge4 / judge3

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	109 ms 5,248 KB
testcase_01	AC	110 ms 5,248 KB
testcase_02	AC	2 ms 5,248 KB
testcase_03	AC	2 ms 5,248 KB
testcase_04	AC	3 ms 5,248 KB
testcase_05	AC	2 ms 5,248 KB
testcase_06	AC	2 ms 5,248 KB
testcase_07	AC	2 ms 5,248 KB
testcase_08	AC	2 ms 5,248 KB
testcase_09	AC	2 ms 5,248 KB
testcase_10	AC	2 ms 5,248 KB
testcase_11	AC	3 ms 5,248 KB
testcase_12	AC	2 ms 5,248 KB
testcase_13	AC	2 ms 5,248 KB
testcase_14	AC	2 ms 5,248 KB
testcase_15	AC	2 ms 5,248 KB
testcase_16	AC	2 ms 5,248 KB
testcase_17	AC	2 ms 5,248 KB
testcase_18	AC	2 ms 5,248 KB
testcase_19	AC	2 ms 5,248 KB
testcase_20	AC	2 ms 5,248 KB
testcase_21	AC	1 ms 5,248 KB
testcase_22	AC	2 ms 5,248 KB
testcase_23	AC	2 ms 5,248 KB
testcase_24	AC	2 ms 5,248 KB
testcase_25	AC	2 ms 5,248 KB
testcase_26	AC	2 ms 5,248 KB
testcase_27	AC	2 ms 5,248 KB
testcase_28	AC	2 ms 5,248 KB
testcase_29	AC	2 ms 5,248 KB
testcase_30	AC	2 ms 5,248 KB
testcase_31	AC	2 ms 5,248 KB
testcase_32	AC	2 ms 5,248 KB
testcase_33	AC	2 ms 5,248 KB
testcase_34	AC	2 ms 5,248 KB
testcase_35	AC	2 ms 5,248 KB

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

ソースコード

raw source code

// #pragma GCC optimize ("O3")
// #pragma GCC target("avx512f")
// #pragma GCC optimize("unroll-loops")
// #ifndef ONLINE_JUDGE
// #define _GLIBCXX_DEBUG
// #endif
#include<bits/stdc++.h>
// #include <boost/multiprecision/cpp_dec_float.hpp>
// #include <boost/multiprecision/cpp_int.hpp>
// #include <boost/rational.hpp>
// namespace mp = boost::multiprecision;
// using Bint=mp::cpp_int;
// using Real = mp::number<mp::cpp_dec_float<64>>;
#include<atcoder/all>
using namespace std;
using namespace atcoder;
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define rep1(n) for(ll i = 0; i < (n); ++i)
#define rep2(i, n) for(ll i = 0; i < (n); ++i)
#define rep3(i, a, b) for(ll i = (a); i < (b); ++i)
#define rep4(i, a, b, c) for(ll i = (a); i < (b); i += (c))
#define rrep(i, a, b) for(ll i = (b); i --> (a); )
int scan(){ return getchar(); }
void scan(int& a){ scanf("%d", &a); }
void scan(unsigned& a){ scanf("%u", &a); }
void scan(long long& a){ scanf("%lld", &a); }
void scan(unsigned long long& a){ scanf("%llu", &a); }
void scan(char& a){ do{ a = getchar(); }while(a == ' ' || a == '\n'); }
void scan(float& a){ scanf("%f", &a); }
void scan(double& a){ scanf("%lf", &a); }
void scan(long double& a){ scanf("%Lf", &a); }
void scan(vector<bool>& a){ for(unsigned i = 0; i < a.size(); i++) { int b; scan(b); a[i] = b; } }
void scan(char a[]){ scanf("%s", a); }
void scan(string& a){ cin >> a; }
template<class T> void scan(vector<T>&);
template<class T> void scan(deque<T>&);
template<class T, size_t size> void scan(array<T, size>&);
template<class T, class L> void scan(pair<T, L>&);
template<class T, size_t size> void scan(T(&)[size]);
template<class T> void scan(vector<T>& a){ for(auto& i : a) scan(i); }
template<class T> void scan(deque<T>& a){ for(auto& i : a) scan(i); }
template<class T, size_t size> void scan(array<T, size>& a){ for(auto& i : a) scan(i); }
template<class T, class L> void scan(pair<T, L>& p){ scan(p.first); scan(p.second); }
template<class T, size_t size> void scan(T (&a)[size]){ for(auto& i : a) scan(i); }
template<class T> void scan(T& a){ cin >> a; }
void in(){}
template <class Head, class... Tail> void in(Head& head, Tail&... tail){ scan(head); in(tail...); }
void print(){ putchar(' '); }
void print(bool a){ printf("%d", a); }
void print(int a){ printf("%d", a); }
void print(unsigned a){ printf("%u", a); }
void print(long long a){ printf("%lld", a); }
void print(unsigned long long a){ printf("%llu", a); }
void print(char a){ printf("%c", a); }
void print(char a[]){ printf("%s", a); }
void print(float a){ printf("%.15f", a); }
void print(double a){ printf("%.15f", a); }
void print(long double a){ printf("%.15Lf", a); }
void print(const string& a){ for(auto&& i : a) print(i); }
template<class T> void print(const vector<T>&);
template<class T, size_t size> void print(const array<T, size>&);
template<class T, class L> void print(const pair<T, L>& p);
template<class T, size_t size> void print(const T (&)[size]);
template<class T> void print(const vector<T>& a){ if(a.empty()) return; print(a[0]); for(auto i = a.begin(); ++i != a.end(); ){ putchar(' '); print(*i); } }
template<class T> void print(const deque<T>& a){ if(a.empty()) return; print(a[0]); for(auto i = a.begin(); ++i != a.end(); ){ putchar(' '); print(*i); } }
template<class T, size_t size> void print(const array<T, size>& a){ print(a[0]); for(auto i = a.begin(); ++i != a.end(); ){ putchar(' '); print(*i); } }
template<class T, class L> void print(const pair<T, L>& p){ print(p.first); putchar(' '); print(p.second); }
template<class T, size_t size> void print(const T (&a)[size]){ print(a[0]); for(auto i = a; ++i != end(a); ){ putchar(' '); print(*i); } }
template<class T> void print(const T& a){ cout << a; }
int out(){ putchar('\n'); return 0; }
template<class T> int out(const T& t){ print(t); putchar('\n'); return 0; }
template<class Head, class... Tail> int out(const Head& head, const Tail&... tail){ print(head); putchar(' '); out(tail...); return 0; }
#define LL(...) ll __VA_ARGS__; in(__VA_ARGS__)
#define STR(...) string __VA_ARGS__; in(__VA_ARGS__)
#define CHR(...) char __VA_ARGS__; in(__VA_ARGS__)
#define DBL(...) double __VA_ARGS__; in(__VA_ARGS__)
#define VEC(type,name,size) vector<type> name(size); in(name)
#define VV(type, name, h, w) vector<vector<type>> name(h, vector<type>(w)); in(name)
#define bit(n,k) (((ll)n>>(ll)k)&1) /*nのk bit目*/
#define pb push_back
#define pf push_front
#define fi first
#define se second
#define eb emplace_back
#define endl '\n'
#define SZ(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define debug(v) cout<<#v<<":";for(auto x:v){cout<<x<<' ';}cout<<endl;
#define pi 3.14159265359
const double eps = 1e-12;
const long long INF= (long long)1e18+20;
const int inf= 1010101010;
typedef long double D;      // 座標値の型。doubleかlong doubleを想定
typedef complex<D> Point;  // Point
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vl>vvl;
typedef vector<vvl>vvvl;
typedef vector<vvvl>vvvvl;
typedef vector<vvvvl>vvvvvl;
typedef vector<int>vi;
typedef vector<vi>vvi;
typedef vector<vvi>vvvi;
typedef vector<vvvi>vvvvi;
typedef vector<vvvvi>vvvvvi;
typedef pair<ll,ll> P;
#define __builtin_popcount __builtin_popcountll
// typedef double D;    
template<class T> using minpq=priority_queue<T,vector<T>,greater<T>>;
// const ll MOD=1000000007LL;
const ll MOD=998244353LL;
// using mint=modint998244353;
using mint=modint;
// using mint=modint1000000007;
// using mint=modint;
typedef vector<mint> vm;
typedef vector<vector<mint> >vvm;
typedef vector<vector<vector<mint> > >vvvm;
//上下右左
vl dx={-1,1,0,0,1,1,-1,-1};
vl dy={0,-0,1,-1,-1,1,-1,1};


template<class T> vector<T> make_vec(size_t a) { return vector<T>(a); }
template<class T, class... Ts> auto make_vec(size_t a, Ts... ts) {
  return vector<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...));
}

template<class T>bool chmax(T &a,const T &b){if(a<b){a=b;return true;}return false;}
template<class T>bool chmin(T &a,const T &b){if(b<a){a=b;return true;}return false;}
template<class T> ll sum(const T& a){ return accumulate(all(a), 0LL); }
template<class T> auto min(const T& a){ return *min_element(all(a)); }
template<class T> auto max(const T& a){ return *max_element(all(a)); }

//素因数分解O(√n)
map<ll,ll>prime_factor(ll n){
  map<ll,ll>res;
  for(ll i=2;i*i<=n;i++){
    while(n%i==0){
      res[i]++;
      n/=i;
    }
  }
  if(n!=1)res[n]=1;
  return res;
}

const ll MAX = 5000010;//5*10^6
long long fac[MAX], finv[MAX], inv[MAX];
//finvが階乗の逆元

// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (ll i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

// 二項係数計算
long long COM(ll n, ll k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}


//素数判定O(√n)
bool is_prime(ll n){
  for(ll i=2;i*i<=n;i++){
    if(n%i==0)return false;
  }
  return n!=1;
}

//約数の列挙O(√n)
vector<ll>divisor(ll n){
  vector<ll>res;
  for(ll i=1;i*i<=n;i++){
    if(n%i==0){
      res.push_back(i);
      if(i != n/i) res.push_back(n/i);
    }
  }
  return res;
}


ll exp(ll n,ll r){
    if(r==0)return 1;
    return n*exp(n,r-1);
}

ll factorial(int n){
    if(n==0)return 1;
    return n*factorial(n-1);
}

template< typename T >
struct Compress {
  vector< T > xs;

  Compress() = default;

  Compress(const vector< T > &vs) {
    add(vs);
  }

  Compress(const initializer_list< vector< T > > &vs) {
    for(auto &p : vs) add(p);
  }

  void add(const vector< T > &vs) {
    copy(begin(vs), end(vs), back_inserter(xs));
  }

  void add(const T &x) {
    xs.emplace_back(x);
  }

  void build() {
    sort(begin(xs), end(xs));
    xs.erase(unique(begin(xs), end(xs)), end(xs));
  }

  vector< int > get(const vector< T > &vs) const {
    vector< int > ret;
    transform(begin(vs), end(vs), back_inserter(ret), [&](const T &x) {
      return lower_bound(begin(xs), end(xs), x) - begin(xs);
    });
    return ret;
  }

  int get(const T &x) const {
    return lower_bound(begin(xs), end(xs), x) - begin(xs);
  }

  const T &operator[](int k) const {
    return xs[k];
  }
};


template<class T>
void rotate90(ll &h,ll &w,vector<vector<T>>&vec){
    vector<vector<T>>vec2(w,vector<T>(h));
    for(int i=0;i<h;i++){
        for(int j=0;j<w;j++){
            vec2[j][h-1-i]=vec[i][j];
        }
    }
    vec=vec2;
    swap(h,w);
}

struct RandomNumberGenerator {
  mt19937 mt;

  RandomNumberGenerator() : mt(chrono::steady_clock::now().time_since_epoch().count()) {}

  int operator()(int a, int b) { // [a, b)
    uniform_int_distribution< int > dist(a, b - 1);
    return dist(mt);
  }

  int operator()(int b) { // [0, b)
    return (*this)(0, b);
  }
};


ll a[100];

// 構文解析
template<typename T>
struct Parser{
    bool error;// ヤバイ時trueに
    Parser():error(false){}
 
    // 四則演算
    T expression(string &s,int &p,int cnt){
        T res=term(s,p,cnt);
        ll cnt2=cnt;
        while(cnt2--){
            if(res.fi>0){
                res.se*=res.fi;
                res.fi--;
            }
            else res.se=0;
        }
        a[res.fi]+=res.se;
        while(p<(int)s.size()){
            if(s[p]=='+'){
                p++;
                res=term(s,p,cnt);
                ll cnt3=cnt;
                while(cnt3--){
                    if(res.fi>0){
                        res.se*=res.fi;
                        res.fi--;
                    }
                    else res.se=0;
                }
                a[res.fi]+=res.se;
                // res+=term(s,p,cnt);
                continue;
            }
            break;
        }
        return {0,0};
    }
 
    // 乗除
    T term(string &s,int &p,int cnt){
        T res=factor(s,p,cnt);
        while(p<(int)s.size()){
            if(s[p]=='*'){
                p++;
                T res2=factor(s,p,cnt);
                res.fi+=res2.fi;
                res.se*=res2.se;
                continue;
            }
            break;
        }
        // cout<<res.fi<<" "<<res.se<<endl;
        // a[res.fi]+=res.se;
        return res;
    }
 
    // カッコ，数
    T factor(string &s,int &p,int cnt){
        T res;
        if(s[p]=='d'){
            p++;
            p++;
            res=expression(s,p,cnt+1);
            p++;
        }else{
            res=number(s,p,cnt+1);
        }
        return res;
    }
 
    // 数，intのみならこれでいい．
    // int以外の数を受け取る場合は適宜編集すること
    T number(string &s,int &p,int cnt){
        T res={0,0};
        if(p<(int)s.size() and isdigit(s[p]))res.se=s[p++]-'0';
        else res.fi++,p++,chmax(res.se,1LL);
        // cout<<res.fi<<" "<<res.se<<endl;
        return res;
    }
 
 
    T execute(string &s){
        int p=0;
        error=false;
        return expression(s,p,0);
    }
};

int main(){
    ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    cout << fixed << setprecision(12);
    //主客転倒！二重和のときは一番内側の物が何回使われるか
    //√Nで分けるテク
    //絶対値は外して2通りの式にした後、変数ごとにまとめる
    //組み合わせが少ないそうなものはdfsで実行してみる（典型25）
    //DはDPのD
    //pow_mod,prime_factor,divisor,is_prime
    // g++ -fsanitize=undefined code.cpp -I.
    // valgrind ./a.out
    /*--------------------------------*/

    ll n;cin>>n;
    ll d;cin>>d;

    string s;cin>>s;
    Parser<P>pt;
    pt.execute(s);
    rep(i,d+1)cout<<a[i]<<" ";
    cout<<endl;

}

yukicoder

結果

テストケース

ソースコード