結果
問題 | No.933 おまわりさんこいつです |
ユーザー | hipopo |
提出日時 | 2020-01-10 18:49:24 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
RE
|
実行時間 | - |
コード長 | 4,272 bytes |
コンパイル時間 | 3,797 ms |
コンパイル使用メモリ | 213,208 KB |
実行使用メモリ | 10,852 KB |
最終ジャッジ日時 | 2024-11-23 22:14:37 |
合計ジャッジ時間 | 8,603 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
10,496 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 | RE | - |
testcase_06 | RE | - |
testcase_07 | RE | - |
testcase_08 | RE | - |
testcase_09 | RE | - |
testcase_10 | RE | - |
testcase_11 | RE | - |
testcase_12 | RE | - |
testcase_13 | RE | - |
testcase_14 | RE | - |
testcase_15 | RE | - |
testcase_16 | RE | - |
testcase_17 | RE | - |
testcase_18 | AC | 2 ms
5,248 KB |
testcase_19 | RE | - |
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 | ^~~~~~~~
ソースコード
#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 = 10, 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; }