#832890 (C++14) No.2188 整数列コイントスゲーム

提出ソース

結果

問題	No.2188 整数列コイントスゲーム
ユーザー	US_cube
提出日時	2023-01-13 22:39:12
言語	C++14 (gcc 12.3.0 + boost 1.83.0)
結果	WA
実行時間	-
コード長	6,214 bytes
コンパイル時間	1,049 ms
コンパイル使用メモリ	103,536 KB
実行使用メモリ	6,948 KB
最終ジャッジ日時	2024-06-06 23:31:51
合計ジャッジ時間	7,066 ms
ジャッジサーバーID （参考情報）	judge3 / judge4

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,812 KB
testcase_01	AC	2 ms 6,940 KB
testcase_02	AC	2 ms 6,944 KB
testcase_03	WA	-
testcase_04	WA	-
testcase_05	AC	2 ms 6,940 KB
testcase_06	WA	-
testcase_07	AC	2 ms 6,944 KB
testcase_08	WA	-
testcase_09	WA	-
testcase_10	WA	-
testcase_11	WA	-
testcase_12	WA	-
testcase_13	WA	-
testcase_14	WA	-
testcase_15	WA	-
testcase_16	WA	-
testcase_17	WA	-
testcase_18	WA	-
testcase_19	WA	-
testcase_20	AC	2 ms 6,940 KB
testcase_21	AC	2 ms 6,944 KB
testcase_22	WA	-
testcase_23	WA	-
testcase_24	WA	-
testcase_25	WA	-
testcase_26	AC	2 ms 6,940 KB
testcase_27	AC	2 ms 6,940 KB
testcase_28	WA	-
testcase_29	WA	-
testcase_30	WA	-
testcase_31	WA	-
testcase_32	WA	-
testcase_33	WA	-
testcase_34	WA	-
testcase_35	WA	-
testcase_36	WA	-
testcase_37	WA	-
testcase_38	WA	-
testcase_39	WA	-
testcase_40	WA	-
testcase_41	WA	-
testcase_42	WA	-
testcase_43	WA	-
testcase_44	WA	-
testcase_45	WA	-
testcase_46	WA	-

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

ソースコード

raw source code

#include <iostream>
#include <cmath>
#include <string>
#include <vector>
#include <algorithm>
#include <utility>
#include <tuple>
#include <cstdint>
#include <cstdio>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <deque>
#include <unordered_map>
#include <unordered_set>
#include <bitset>
#include <cctype>
#include <climits>
#include <functional>
#include <cassert>
#include <numeric>
#define rep(i, n) for(int i = 0; i < (n); i++)
#define per(i, n) for(int i = (n) - 1; i >= 0; i--)
using ll = long long;
#define vi vector<int>
#define vvi vector<vi>
#define vl vector<ll>
#define pii pair<int, int>
#define pll pair<ll, ll>
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
constexpr int mod = 1000000007;
using namespace std;
template<class T, class U>
bool chmax(T &a, const U &b){ return a < b ? (a = b, 1) : 0; }
template<class T, class U>
bool chmin(T &a, const U &b){ return a > b ? (a = b, 1) : 0; }
struct bint {
  private:
  static constexpr int BASE = 100000000;
  static constexpr int LEN = 8; //log10(BASE)
  bool negative;
  vector<int> a;
  int n = 0;
  bint &normalize(){
    int i = n - 1;
    while(i >= 0 && a[i] == 0) i--;
    a.resize(i + 1);
    n = i + 1;
    if(n == 0) negative = false;
    return *this;
  }
  public:
  bint(int x = 0) : negative(x < 0){
    if(negative) x = -x;
    for(; x > 0; x /= BASE){
      a.push_back(x % BASE);
      n++;
    }
  }
  bint(const string &s) : negative(false){
    int p = 0;
    if(s[p] == '-'){
      p++;
      negative = true;
    }
    else if(s[p] == '+') p++;
    for(int i = s.size() - 1, v = BASE; i >= p; i--, v *= 10){
      int x = s[i] - '0';
      if(x < 0 || 9 < x){
        cerr << "error: parse error:" << s << "\n";
        exit(1);
      } 
      if(v == BASE){
        v = 1;
        a.push_back(x);
        n++;
      }else a.back() += x * v;
    }
    normalize();
  }
  bint &operator=(const bint& x){
    negative = x.negative;
    a = x.a; n = x.n;
    return *this;
  }
  bint &operator=(int x){ return *this = bint(x); }
  bint &operator=(const std::string &s){ return *this = bint(s); }
  const bool operator<(const bint &x) const{
    if(negative != x.negative) return negative < x.negative;
    if(n != x.n) return (n < x.n) ^ negative;
    for(int i = n - 1; i >= 0; i--)
      if(a[i] != x.a[i]) return (a[i] < x.a[i]) ^ negative;
    return false;
  }
  const bool operator>(const bint& x) const{ return x < (*this); }
  const bool operator<=(const bint& x) const{ return !(x < (*this)); }
  const bool operator>=(const bint& x) const{ return !((*this) < x); }
  const bool operator!=(const bint& x) const{ return (*this) < x || x < (*this); }
  const bool operator==(const bint& x) const{ return !((*this) < x || x < (*this)); }
  bint operator-() const{
    bint ret(*this);
    if(n) ret.negative = !ret.negative;
    return ret;
  }
  bint &operator+=(const bint& x){
    if(negative != x.negative) return *this -= -x;
    if(n < x.n){
      a.resize(x.n);
      n = x.n;
    }
    int tmp = 0;
    for(int i = 0; i < n; i++){
      a[i] += (i < x.n ? x.a[i] : 0) + tmp;
      tmp = a[i] / BASE;
      a[i] %= BASE;
    }
    if(tmp){
      a.push_back(1);
      n++;
    }
    return *this;
  }
  bint &operator-=(const bint &x){
    if(negative != x.negative) return *this += -x;
    vector<int> b(x.a);
    int bn = b.size();
    if((*this < x) ^ negative){
      a.swap(b);
      swap(n, bn);
      negative = !negative;
    }
    for(int i = 0, tmp = 0; i < n; i++){
      a[i] += BASE - (i < bn ? b[i] : 0) + tmp;
      tmp = a[i] / BASE - 1;
      a[i] %= BASE;
    }
    return this->normalize();
  }
  bint &operator*=(const bint &x){
    negative ^= x.negative;
    vector<int> c(n * x.n + 1);
    for(int i = 0; i < n; i++){
      ll tmp = 0;
      for(int j = 0; j < x.n; j++){
        ll v = (ll)a[i] * x.a[j] + c[i+j] + tmp;
        tmp = v / BASE;
        c[i+j] = (int)(v % BASE);
      }
      if(tmp) c[i + x.n] += (int)tmp;
    }
    a.swap(c);
    n = a.size();
    return this->normalize();
  }
  bint &operator/=(const bint &x){
    return *this = divmod(*this, x).first;
  }
  bint &operator%=(const bint &x){
    return *this = divmod(*this, x).second;
  }
  const bint operator+(const bint &x) const{
    bint res(*this); return res += x;
  }
  const bint operator-(const bint &x) const{
    bint res(*this); return res -= x;
  }
  const bint operator*(const bint &x) const{
    bint res(*this); return res *= x;
  }
  const bint operator/(const bint &x) const{
    bint res(*this); return res /= x;
  }
  const bint operator%(const bint &x) const{
    bint res(*this); return res %= x;
  }
  pair<bint,bint> divmod(const bint &lhs, const bint &rhs){
    if(!rhs.n){
      cerr << "error: division by zero\n";
      exit(1);
    }
    bint x(abs(rhs)), q, r;
    for(int i = lhs.n - 1; i >= 0; i--){
      r = r * BASE + lhs.a[i];
      int left = 0, right = BASE;
      if(r >= x){
        while(left + 1 < right){
          int mid = (left + right) / 2;
          if(x * bint(mid) > r) right = mid;
          else left = mid;
        }
        r -= x * left;
      }
      q.a.push_back(left);
      q.n++;
    }
    reverse(q.a.begin(), q.a.end());
    bool neg = lhs.negative ^ lhs.negative;
    q.negative = neg; r.negative = neg;
    return { q.normalize(), r.normalize() };
  }
  string to_string() const{
    string s;
    if(negative) s += '-';
    if(!n) s += '0';
    else s += std::to_string(a.back());
    for(int i = n - 2; i >= 0; i--){
      const string t = std::to_string(a[i]);
      s += string(LEN - t.size(), '0');
      s += t;
    }
    return s;
  }
  friend istream &operator>>(istream &is, bint &x){
    string tmp; is >> tmp;
    x = bint(tmp);
    return is;
  }
  friend ostream &operator<<(ostream &os, const bint &x){
    if(x.negative) os << '-';
    if(!x.n) os << 0;
    else os << x.a.back();
    for(int i = x.n - 2; i >= 0; i--){
      os.width(LEN);
      os.fill('0');
      os << x.a[i];
    }
    return os;
  }
  const bint abs(bint x){
    x.negative = false;
    return x;
  }
};
int main(){
  int n,m;
  cin >> n >> m;
  bint ans = 1;
  rep(i, n) ans *= m;
  cout << ans << "\n";
}

yukicoder

結果

テストケース

ソースコード