#710698 (C++17) No.1677 mæx

提出ソース

結果

問題	No.1677 mæx
ユーザー	re_re0101
提出日時	2021-10-27 07:00:42
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	10 ms / 2,000 ms
コード長	11,790 bytes
コンパイル時間	4,822 ms
コンパイル使用メモリ	276,928 KB
実行使用メモリ	9,808 KB
最終ジャッジ日時	2024-10-07 01:07:26
合計ジャッジ時間	5,111 ms
ジャッジサーバーID （参考情報）	judge1 / judge4

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 5,248 KB
testcase_01	AC	1 ms 5,248 KB
testcase_02	AC	2 ms 5,248 KB
testcase_03	AC	2 ms 5,248 KB
testcase_04	AC	9 ms 7,936 KB
testcase_05	AC	9 ms 7,936 KB
testcase_06	AC	8 ms 8,064 KB
testcase_07	AC	9 ms 7,932 KB
testcase_08	AC	8 ms 7,936 KB
testcase_09	AC	8 ms 7,936 KB
testcase_10	AC	9 ms 7,936 KB
testcase_11	AC	9 ms 7,880 KB
testcase_12	AC	9 ms 7,808 KB
testcase_13	AC	9 ms 7,796 KB
testcase_14	AC	8 ms 7,880 KB
testcase_15	AC	9 ms 7,936 KB
testcase_16	AC	9 ms 7,936 KB
testcase_17	AC	9 ms 7,936 KB
testcase_18	AC	8 ms 7,884 KB
testcase_19	AC	1 ms 5,248 KB
testcase_20	AC	2 ms 5,248 KB
testcase_21	AC	10 ms 9,808 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 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=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);
}


pair<long long,long long>roop_search(vl next_index,ll first_point){
	ll idx=first_point;
	map<ll,ll>mp;
	mp[idx]=0;
	ll cur=1;
	ll roop_begin=-1;
	ll roop_size=-1;
	while(true){
		idx=next_index[idx];
		if(mp.count(idx)){
			roop_begin=mp[idx];
			roop_size=cur-roop_begin;
			break;
		}
		mp[idx]=cur++;
	}
	return {roop_begin,roop_size};
}


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);
  }
};

void f(ll &a){
    string s=to_string(a);
    if(s.size()==2){
        cout<<s;
    }
    else {
        cout<<0<<s;
    }
    return;
}

#define vl vm

struct Parser{
    bool error;
    Parser():error(false){}

    vl expression(string &s,int &p){
        vl vec(3);
        if(p==s.size()){
            return vec;
        }
        if(s[p]=='m'){
            p++;
            char c=s[p];
            vl vec1,vec2;
            p+=3;
            vec1=expression(s,p);
            mint sum1=0;
            rep(i,3)sum1+=vec1[i];
            p+=1;
            vec2=expression(s,p);
            mint sum2=0;
            rep(i,3)sum2+=vec2[i];
            p+=1;
            if(c=='a'||c=='?'){
                vec[0]+=vec1[0]*vec2[0];
                vec[1]+=vec1[1]*vec2[1]+vec1[1]*vec2[0]+vec1[0]*vec2[1];
                vec[2]+=vec1[2]*vec2[2]+vec1[2]*vec2[1]+vec1[2]*vec2[0]+vec1[1]*vec2[2]+vec1[0]*vec2[2];
            }
            // debug(vec1);
            // debug(vec2);
            if(c=='e'||c=='?'){
                vec[2]+=vec1[0]*vec2[1]+vec1[1]*vec2[0];
                vec[1]+=vec1[0]*vec2[2]+vec1[2]*vec2[0]+vec1[0]*vec2[0];
                vec[0]+=sum1*sum2-(vec1[0]*vec2[1]+vec1[1]*vec2[0])-(vec1[0]*vec2[2]+vec1[2]*vec2[0]+vec1[0]*vec2[0]);
            }
            return vec;
            
        }
        else {
            return number(s,p);
        }
    }
 
    vl number(string &s,int &p){
        vl vec(3);
        if(s[p]=='?'){
            vec[0]=1;
            vec[1]=1;
            vec[2]=1;
        }
        else if(s[p]=='1'){
            vec[1]=1;
        }
        else if(s[p]=='2'){
            vec[2]=1;
        }
        else vec[0]=1;
        // cout<<s[p]<<endl;
        // debug(vec);
        p++;
        return vec;
    }
 
 
    vl execute(string &s){
        int p=0;
        error=false;
        return expression(s,p);
    }
};

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
    /*--------------------------------*/

    string s;cin>>s;
    ll k;cin>>k;
    Parser ps;
    cout<<(ps.execute(s)[k]).val()<<endl;
    
    

}

yukicoder

結果

テストケース

ソースコード