結果

問題 No.933 おまわりさんこいつです
ユーザー hipopohipopo
提出日時 2020-01-10 18:50:45
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
TLE  
実行時間 -
コード長 4,277 bytes
コンパイル時間 2,958 ms
コンパイル使用メモリ 213,048 KB
実行使用メモリ 10,496 KB
最終ジャッジ日時 2024-11-23 22:14:50
合計ジャッジ時間 10,581 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
9,612 KB
testcase_01 AC 2 ms
5,248 KB
testcase_02 AC 2 ms
5,248 KB
testcase_03 AC 2 ms
5,248 KB
testcase_04 AC 2 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 4 ms
5,248 KB
testcase_13 AC 29 ms
5,248 KB
testcase_14 AC 56 ms
5,248 KB
testcase_15 AC 274 ms
5,248 KB
testcase_16 TLE -
testcase_17 AC 78 ms
5,248 KB
testcase_18 AC 2 ms
5,248 KB
testcase_19 AC 795 ms
5,248 KB
testcase_20 TLE -
testcase_21 AC 2 ms
5,248 KB
testcase_22 AC 2 ms
5,248 KB
testcase_23 RE -
testcase_24 RE -
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp:40:3: warning: converting 'bigint' to a base class 'std::vector<long long int>' will never use a type conversion operator [-Wclass-conversion]
   40 |   operator vector<long long>(); // protect from unexpected casts
      |   ^~~~~~~~

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

struct bigint : vector<long long> {
  // smaller B ==> larger deals / slower operations
  // B = 100000000  (10^8) ==> it deals with 10^645636
  // B = 1000000000 (10^9) ==> it deals with 10^7378
  static constexpr int B = 1000000, W = log10(B);
  char sign;
  bigint& trim() {
    while (!empty() && !back()) pop_back();
    if (empty()) sign = 1;
    return *this;
  }
  bigint(long long v = 0) : sign(1) {
    if (v < 0) { sign = -1; v = -v; }
    while (v > 0) {
      push_back(v % B);
      v /= B;
    }
  }
  bigint(string s) : sign(+1) {
    int e = 0;
    for (; e < s.size() && s[e] <= '0' || s[e] >= '9'; ++e)
      if (s[e] == '-') sign = -sign;
    for (int i = s.size()-1; i >= e; i -= W) {
      push_back(0);
      for (int j = max(e, i - W + 1); j <= i; ++j)
        back() = 10 * back() + (s[j] - '0');
    }
    trim();
  }
  bigint operator-() const {
    bigint x = *this;
    if (!empty()) x.sign = -x.sign;
    return x;
  }
  operator vector<long long>(); // protect from unexpected casts

  bigint &operator+=(bigint x);
};

// input and output
ostream &operator<<(ostream &os, const bigint &x) {
  if (x.sign < 0) os << '-';
  os << (x.empty() ? 0 : x.back());
  for (int i = (int)x.size()-2; i >= 0; --i) 
    os << setfill('0') << setw(bigint::W) << x[i];
  return os;
}
istream &operator>>(istream &is, bigint &x) {
  string s;
  is >> s;
  x = bigint(s);
  return is;
}

bigint operator-(bigint x, bigint y);
bigint operator+(bigint x, bigint y) {
  if (x.sign != y.sign) return x - (-y);
  if (x.size() < y.size()) swap(x, y);
  int c = 0;
  for (int i = 0; i < y.size(); ++i) {
    x[i] += y[i] + c;
    c = (x[i] >= bigint::B);
    if (c) x[i] -= bigint::B;
  }
  if (c) x.push_back(c);
  return x;
}
bigint operator-(bigint x, bigint y) {
  if (x.sign != y.sign) return x + (-y);
  int sign = x.sign;
  x.sign = y.sign = +1;
  if (x < y) {
    swap(x, y); 
    sign = -sign;
  }
  int c = 0;
  for (int i = 0; i < x.size(); ++i) {
    x[i] -= (i < y.size() ? y[i] : 0) + c;
    c = (x[i] < 0);
    if (c) x[i] += bigint::B;
  }
  x.sign = sign;
  return x.trim(); 
}
bigint operator*(bigint x, int y) {
  if (y == 0) return bigint(0);
  if (y < 0) { x.sign = -x.sign; y = -y; }
  int c = 0;
  for (int i = 0; i < x.size() || c; ++i) {
    if (i == x.size()) x.push_back(0);
    x[i] = x[i] * y + c;
    c = x[i] / bigint::B;
    if (c) x[i] %= bigint::B; 
  }
  return x;
}
bigint operator*(int x, bigint y) { return y * x; }

// Karatsuba multiplication
bigint operator*(bigint x, bigint y) {
  if (x.empty()||y.empty()) return bigint(0);
  function<void(long long*, int, long long*, int, long long*)>
    rec = [&](long long *x, int xn, long long *y, int yn, long long *z) {
    if (xn < yn) { swap(xn, yn); swap(x, y); }
    fill(z, z+xn+yn, 0);
    if (yn <= 2) {
      for (int i = 0; i < xn; ++i) 
        for (int j = 0; j < yn; ++j) 
          z[i+j] += x[i] * y[j];
    } else {
      int m = (xn+1)/2, n = min(m, yn);
      for (int i = 0; i+m < xn; ++i) x[i] += x[i+m];
      for (int j = 0; j+m < yn; ++j) y[j] += y[j+m];
      rec(x, m, y, n, z+m);
      for (int i = 0; i+m < xn; ++i) x[i] -= x[i+m];
      for (int j = 0; j+m < yn; ++j) y[j] -= y[j+m];
      long long p[2*m+2];
      rec(x, m, y, n, p);
      for (int i = 0; i < m+n; ++i) { z[i] += p[i]; z[i+m] -= p[i]; }
      rec(x+m, xn-m, y+m, yn-n, p); 
      for (int i = 0; i < xn+yn-m-n; ++i) { z[i+m] -= p[i]; z[i+2*m] += p[i]; }
    }
  };
  bigint z; z.resize(x.size()+y.size()+2);
  z.sign = x.sign * y.sign;
  rec(&x[0], x.size(), &y[0], y.size(), &z[0]);
  for (int i = 0; i+1 < z.size(); ++i) { // be careful with overflow
    z[i+1] += z[i] / bigint::B;
    z[i] %= bigint::B;
    if (z[i] < 0) { 
      z[i+1] -= 1;
      z[i] += bigint::B;
    }
  }
  return z.trim();
}

int calc(ll x) {
    if (x < 10) return x;

    ll sum = 0;
    while (0 < x) {
        sum += x % 10;
        x /= 10;
    }

    return calc(sum);
}

int main() {
    int n;
    cin >> n;
    bigint res(1ll);
    for (int i = 0; i < n; i++) {
        ll a;
        cin >> a;
        res = res * bigint(a);
    }
    
    ll sum = 0;
    for (ll d: res) {
        sum += d;
    }

    cout << calc(sum) << endl;
}
0