QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#767064 | #9225. Fibonacci Fusion | Misuki | AC ✓ | 2419ms | 737688kb | C++20 | 16.4kb | 2024-11-20 19:43:01 | 2024-11-20 19:43:02 |
Judging History
answer
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <cctype>
#include <cfenv>
#include <cfloat>
#include <chrono>
#include <cinttypes>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdarg>
#include <cstddef>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <deque>
#include <fstream>
#include <functional>
#include <initializer_list>
#include <iomanip>
#include <ios>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <stack>
#include <streambuf>
#include <string>
#include <tuple>
#include <type_traits>
#include <variant>
#include <bit>
#include <compare>
#include <concepts>
#include <numbers>
#include <ranges>
#include <span>
//#define int ll
#define INT128_MAX (__int128)(((unsigned __int128) 1 << ((sizeof(__int128) * __CHAR_BIT__) - 1)) - 1)
#define INT128_MIN (-INT128_MAX - 1)
#define clock chrono::steady_clock::now().time_since_epoch().count()
using namespace std;
template<class T1, class T2>
ostream& operator<<(ostream& os, const pair<T1, T2> pr) {
return os << pr.first << ' ' << pr.second;
}
template<class T, size_t N>
ostream& operator<<(ostream& os, const array<T, N> &arr) {
for(size_t i = 0; T x : arr) {
os << x;
if (++i != N) os << ' ';
}
return os;
}
template<class T>
ostream& operator<<(ostream& os, const vector<T> &vec) {
for(size_t i = 0; T x : vec) {
os << x;
if (++i != size(vec)) os << ' ';
}
return os;
}
template<class T>
ostream& operator<<(ostream& os, const set<T> &s) {
for(size_t i = 0; T x : s) {
os << x;
if (++i != size(s)) os << ' ';
}
return os;
}
template<class T1, class T2>
ostream& operator<<(ostream& os, const map<T1, T2> &m) {
for(size_t i = 0; pair<T1, T2> x : m) {
os << x;
if (++i != size(m)) os << ' ';
}
return os;
}
#ifdef DEBUG
#define dbg(...) cerr << '(', _do(#__VA_ARGS__), cerr << ") = ", _do2(__VA_ARGS__)
template<typename T> void _do(T &&x) { cerr << x; }
template<typename T, typename ...S> void _do(T &&x, S&&...y) { cerr << x << ", "; _do(y...); }
template<typename T> void _do2(T &&x) { cerr << x << endl; }
template<typename T, typename ...S> void _do2(T &&x, S&&...y) { cerr << x << ", "; _do2(y...); }
#else
#define dbg(...)
#endif
using ll = long long;
using ull = unsigned long long;
using ldb = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
//#define double ldb
template<typename T> using min_heap = priority_queue<T, vector<T>, greater<T>>;
template<typename T> using max_heap = priority_queue<T>;
template<ranges::forward_range rng, class T = ranges::range_value_t<rng>, class OP = plus<T>>
void pSum(rng &&v) {
if (!v.empty())
for(T p = v[0]; T &x : v | views::drop(1))
x = p = OP()(p, x);
}
template<ranges::forward_range rng, class T = ranges::range_value_t<rng>, class OP>
void pSum(rng &&v, OP op) {
if (!v.empty())
for(T p = v[0]; T &x : v | views::drop(1))
x = p = op(p, x);
}
template<ranges::forward_range rng>
void Unique(rng &v) {
ranges::sort(v);
v.resize(unique(v.begin(), v.end()) - v.begin());
}
template<ranges::random_access_range rng>
rng invPerm(rng p) {
rng ret = p;
for(int i = 0; i < ssize(p); i++)
ret[p[i]] = i;
return ret;
}
template<ranges::random_access_range rng, ranges::random_access_range rng2>
rng Permute(rng v, rng2 p) {
rng ret = v;
for(int i = 0; i < ssize(p); i++)
ret[p[i]] = v[i];
return ret;
}
template<bool directed>
vector<vector<int>> readGraph(int n, int m, int base) {
vector<vector<int>> g(n);
for(int i = 0; i < m; i++) {
int u, v; cin >> u >> v;
u -= base, v -= base;
g[u].emplace_back(v);
if constexpr (!directed)
g[v].emplace_back(u);
}
return g;
}
template<class T>
void setBit(T &msk, int bit, bool x) {
msk = (msk & ~(T(1) << bit)) | (T(x) << bit);
}
template<class T> void flipBit(T &msk, int bit) { msk ^= T(1) << bit; }
template<class T> bool getBit(T msk, int bit) { return msk >> bit & T(1); }
template<class T>
T floorDiv(T a, T b) {
if (b < 0) a *= -1, b *= -1;
return a >= 0 ? a / b : (a - b + 1) / b;
}
template<class T>
T ceilDiv(T a, T b) {
if (b < 0) a *= -1, b *= -1;
return a >= 0 ? (a + b - 1) / b : a / b;
}
template<class T> bool chmin(T &a, T b) { return a > b ? a = b, 1 : 0; }
template<class T> bool chmax(T &a, T b) { return a < b ? a = b, 1 : 0; }
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef vector<int> vi;
//reference: https://github.com/NyaanNyaan/library/blob/master/modint/montgomery-modint.hpp#L10
//note: mod should be a prime less than 2^30.
template<uint32_t mod>
struct MontgomeryModInt {
using mint = MontgomeryModInt;
using i32 = int32_t;
using u32 = uint32_t;
using u64 = uint64_t;
static constexpr u32 get_r() {
u32 res = 1, base = mod;
for(i32 i = 0; i < 31; i++)
res *= base, base *= base;
return -res;
}
static constexpr u32 get_mod() {
return mod;
}
static constexpr u32 n2 = -u64(mod) % mod; //2^64 % mod
static constexpr u32 r = get_r(); //-P^{-1} % 2^32
u32 a;
static u32 reduce(const u64 &b) {
return (b + u64(u32(b) * r) * mod) >> 32;
}
static u32 transform(const u64 &b) {
return reduce(u64(b) * n2);
}
MontgomeryModInt() : a(0) {}
MontgomeryModInt(const int64_t &b)
: a(transform(b % mod + mod)) {}
mint pow(u64 k) const {
mint res(1), base(*this);
while(k) {
if (k & 1)
res *= base;
base *= base, k >>= 1;
}
return res;
}
mint inverse() const { return (*this).pow(mod - 2); }
u32 get() const {
u32 res = reduce(a);
return res >= mod ? res - mod : res;
}
mint& operator+=(const mint &b) {
if (i32(a += b.a - 2 * mod) < 0) a += 2 * mod;
return *this;
}
mint& operator-=(const mint &b) {
if (i32(a -= b.a) < 0) a += 2 * mod;
return *this;
}
mint& operator*=(const mint &b) {
a = reduce(u64(a) * b.a);
return *this;
}
mint& operator/=(const mint &b) {
a = reduce(u64(a) * b.inverse().a);
return *this;
}
mint operator-() { return mint() - mint(*this); }
bool operator==(mint b) const {
return (a >= mod ? a - mod : a) == (b.a >= mod ? b.a - mod : b.a);
}
bool operator!=(mint b) const {
return (a >= mod ? a - mod : a) != (b.a >= mod ? b.a - mod : b.a);
}
friend mint operator+(mint c, mint d) { return c += d; }
friend mint operator-(mint c, mint d) { return c -= d; }
friend mint operator*(mint c, mint d) { return c *= d; }
friend mint operator/(mint c, mint d) { return c /= d; }
friend ostream& operator<<(ostream& os, const mint& b) {
return os << b.get();
}
friend istream& operator>>(istream& is, mint& b) {
int64_t val;
is >> val;
b = mint(val);
return is;
}
};
using mint = MontgomeryModInt<998244353>;
//reference: https://judge.yosupo.jp/submission/69896
//remark: MOD = 2^K * C + 1, R is a primitive root modulo MOD
//remark: a.size() <= 2^K must be satisfied
//some common modulo: 998244353 = 2^23 * 119 + 1, R = 3
// 469762049 = 2^26 * 7 + 1, R = 3
// 1224736769 = 2^24 * 73 + 1, R = 3
template<int32_t k = 23, int32_t c = 119, int32_t r = 3, class Mint = MontgomeryModInt<998244353>>
struct NTT {
using u32 = uint32_t;
static constexpr u32 mod = (1 << k) * c + 1;
static constexpr u32 get_mod() { return mod; }
static void ntt(vector<Mint> &a, bool inverse) {
static array<Mint, 30> w, w_inv;
if (w[0] == 0) {
Mint root = 2;
while(root.pow((mod - 1) / 2) == 1) root += 1;
for(int i = 0; i < 30; i++)
w[i] = -(root.pow((mod - 1) >> (i + 2))), w_inv[i] = 1 / w[i];
}
int n = ssize(a);
if (not inverse) {
for(int m = n; m >>= 1; ) {
Mint ww = 1;
for(int s = 0, l = 0; s < n; s += 2 * m) {
for(int i = s, j = s + m; i < s + m; i++, j++) {
Mint x = a[i], y = a[j] * ww;
a[i] = x + y, a[j] = x - y;
}
ww *= w[__builtin_ctz(++l)];
}
}
} else {
for(int m = 1; m < n; m *= 2) {
Mint ww = 1;
for(int s = 0, l = 0; s < n; s += 2 * m) {
for(int i = s, j = s + m; i < s + m; i++, j++) {
Mint x = a[i], y = a[j];
a[i] = x + y, a[j] = (x - y) * ww;
}
ww *= w_inv[__builtin_ctz(++l)];
}
}
Mint inv = 1 / Mint(n);
for(Mint &x : a) x *= inv;
}
}
static vector<Mint> conv(vector<Mint> a, vector<Mint> b) {
int sz = ssize(a) + ssize(b) - 1;
int n = bit_ceil((u32)sz);
a.resize(n, 0);
ntt(a, false);
b.resize(n, 0);
ntt(b, false);
for(int i = 0; i < n; i++)
a[i] *= b[i];
ntt(a, true);
a.resize(sz);
return a;
}
};
//#include<modint/MontgomeryModInt.cpp>
//#include<poly/NTTmint.cpp>
template<bool fast_mul = true>
struct bigint {
int sgn;
vector<int> val;
static constexpr int LOG = fast_mul ? 1 : 9;
static constexpr int W = fast_mul ? 10 : 1'000'000'000;
bigint(string s = "0") {
if (!s.empty() and s[0] == '-') {
sgn = -1;
s.erase(s.begin());
} else {
sgn = 1;
}
s.insert(0, (LOG - ssize(s) % LOG) % LOG, '0');
if (s.empty()) s = string(LOG, '0');
val.resize(size(s) / LOG);
ranges::reverse(s);
for(int i = ssize(s) - 1; i >= 0; i--)
val[i / LOG] = val[i / LOG] * 10 + (s[i] - '0');
}
int log10() {
assert(sgn == 1);
int x = LOG * (ssize(val) - 1), y = val.back();
while(y) x++, y /= 10;
return x - 1;
}
void norm() {
if (sgn == -1 and ssize(val) == 1 and val[0] == 0)
sgn = 1;
}
bool abs_less(const bigint &b) const {
if (size(val) != size(b.val))
return size(val) < size(b.val);
for(int i = ssize(val) - 1; i >= 0; i--)
if (val[i] != b.val[i])
return val[i] < b.val[i];
return false;
}
bigint& operator+=(const bigint &b) {
if (sgn != b.sgn) {
*this -= -b;
} else if (abs_less(b)) {
*this = b + *this;
} else {
for(int i = 0; i < min(ssize(val), ssize(b.val)); i++) {
val[i] += b.val[i];
if (int q = val[i] / W; q > 0) {
if (i + 1 == ssize(val)) val.emplace_back();
val[i] -= q * W, val[i + 1] += q;
}
}
int j = min(ssize(val), ssize(b.val));
while(j < ssize(val) and val[j] >= W) {
int q = val[j] / W;
if (j + 1 == ssize(val)) val.emplace_back();
val[j] -= q * W, val[j + 1] += q, j++;
}
}
norm();
return *this;
}
bigint& operator-=(const bigint &b) {
if (sgn != b.sgn) {
*this += -b;
} else if (abs_less(b)) {
*this = b - *this, sgn = -sgn;
} else {
for(int i = 0; i < min(ssize(val), ssize(b.val)); i++) {
val[i] -= b.val[i];
if (val[i] < 0)
val[i] += W, val[i + 1] -= 1;
}
int j = min(ssize(val), ssize(b.val));
while(j < ssize(val) and val[j] < 0)
val[j] += W, val[j + 1] -= 1, j++;
while(ssize(val) > 1 and val.back() == 0) val.pop_back();
}
norm();
return *this;
}
bigint& operator*=(const bigint &b) {
if constexpr (LOG == 1) {
static NTT ntt;
vector<mint> c(size(val)), d(size(b.val));
for(int i = 0; i < ssize(c); i++) c[i] = val[i];
for(int i = 0; i < ssize(d); i++) d[i] = b.val[i];
c = ntt.conv(c, d);
vector<int> tmp(ssize(c));
for(int i = 0; i < ssize(c); i++)
tmp[i] = c[i].get();
for(int i = 0; i < ssize(tmp); i++) {
if (int q = tmp[i] / W; q > 0) {
if (i + 1 == ssize(tmp)) tmp.emplace_back();
tmp[i] -= q * W, tmp[i + 1] += q;
}
}
val.swap(tmp);
} else {
vector<int> tmp(ssize(val) + ssize(b.val) + 1);
for(int i = 0; i < ssize(val); i++) {
for(int j = 0; j < ssize(b.val); j++) {
if (int q = tmp[i + j] / W; q > 0)
tmp[i + j] -= q * W, tmp[i + j + 1] += q;
ll x = (ll)val[i] * b.val[j];
tmp[i + j] += x % W, tmp[i + j + 1] += x / W;
if (int q = tmp[i + j] / W; q > 0)
tmp[i + j] -= q * W, tmp[i + j + 1] += q;
}
}
val.swap(tmp);
}
while(ssize(val) > 1 and val.back() == 0) val.pop_back();
sgn *= b.sgn;
norm();
return *this;
}
bool operator<(const bigint &b) {
if (sgn != b.sgn) return sgn == -1;
else if (sgn == 1) return abs_less(b);
else return b.abs_less(*this);
}
bool operator>(const bigint &b) { return b < *this; }
bool operator<=(const bigint &b) { return !(*this > b); }
bool operator>=(const bigint &b) { return !(*this < b); }
bool operator==(const bigint &b) { return sgn == b.sgn and val == b.val; }
friend bigint operator+(bigint a, bigint b) { return a += b; }
friend bigint operator-(bigint a, bigint b) { return a -= b; }
friend bigint operator*(bigint a, bigint b) { return a *= b; }
bigint operator-() const {
bigint b = *this;
b.sgn = -b.sgn;
return b;
}
string to_string() const {
string s;
for(int i = 0; i < ssize(val); i++) {
int x = val[i];
for(int j = 0; j < LOG; j++)
s += '0' + (x % 10), x /= 10;
}
while(ssize(s) > 1 and s.back() == '0') s.pop_back();
if (sgn == -1) s += '-';
ranges::reverse(s);
return s;
}
friend ostream& operator<<(ostream& os, const bigint& b) {
return os << b.to_string();
}
};
//source: KACTL(https://github.com/kth-competitive-programming/kactl)
ull modmul(ull a, ull b, ull M) {
ll ret = a * b - M * ull(1.L / M * a * b);
return ret + M * (ret < 0) - M * (ret >= (ll)M);
}
ull modpow(ull b, ull e, ull mod) {
ull ans = 1;
for (; e; b = modmul(b, b, mod), e /= 2)
if (e & 1) ans = modmul(ans, b, mod);
return ans;
}
bool isPrime(ull n) {
if (n < 2 || n % 6 % 4 != 1) return (n | 1) == 3;
ull A[] = {2, 325, 9375, 28178, 450775, 9780504, 1795265022},
s = __builtin_ctzll(n-1), d = n >> s;
for (ull a : A) { // ^ count trailing zeroes
ull p = modpow(a%n, d, n), i = s;
while (p != 1 && p != n - 1 && a % n && i--)
p = modmul(p, p, n);
if (p != n-1 && i != s) return 0;
}
return 1;
}
template<class T, size_t N>
array<T, N>& operator+=(array<T, N> &a, const array<T, N> &b) {
for(size_t i = 0; i < N; i++)
a[i] += b[i];
return a;
}
template<class T, size_t N>
array<T, N>& operator-=(array<T, N> &a, const array<T, N> &b) {
for(size_t i = 0; i < N; i++)
a[i] -= b[i];
return a;
}
template<class T, size_t N>
array<T, N> operator+(array<T, N> a, array<T, N> b) { return a += b; }
template<class T, size_t N>
array<T, N> operator-(array<T, N> a, array<T, N> b) { return a -= b; }
using B = bigint<true>;
using HA = array<int, 16>;
mt19937 rng(clock);
uniform_int_distribution<int> unif(500'000'000, 1'000'000'000);
HA m;
HA fromB(B a) {
HA r = {};
for(int i = 0; i < 16; i++)
for(ll base = 1; int x : a.val)
r[i] = (r[i] + base * x) % m[i], base = base * B::W % m[i];
return r;
}
HA fib[11'000'000];
signed main() {
ios::sync_with_stdio(false), cin.tie(NULL);
for(int &x : m) while(!isPrime(x = unif(rng))) ;
fill(fib[1].begin(), fib[1].end(), 1);
for(int i = 2; i < 11'000'000; i++)
for(int j = 0; j < 16; j++)
fib[i][j] = (fib[i - 1][j] + fib[i - 2][j]) % m[j];
int n; cin >> n;
vector<B> a(n);
for(int i = 0; i < n; i++) {
string s; cin >> s;
a[i] = B(s);
}
sort(a.begin(), a.end(), [](B &a, B &b) { return a < b; });
ll ans = 0;
map<HA, int> f;
for(int i = 0; i < n; i++) {
int k = a[i].log10() / log10l((1 + sqrtl(5)) / 2);
dbg(a[i], k);
auto tmp = fromB(a[i]);
for(int l = max(k - 10, 2); l <= k + 16; l++) {
auto tar = fib[l] - tmp;
for(int j = 0; j < 16; j++) tar[j] = (tar[j] % m[j] + m[j]) % m[j];
if (f.contains(tar)) ans += f[tar];
}
f[tmp]++;
}
cout << ans << '\n';
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 314ms
memory: 691044kb
input:
6 50 8 8 5 72 354224848179261915070
output:
4
result:
ok 1 number(s): "4"
Test #2:
score: 0
Accepted
time: 812ms
memory: 711544kb
input:
28 200878223506436882933619847964496455022155117513398820563747455993172799881403389571477889821109288771413214004090719097929400406252135763028179112130390003528046316900603668569910008417315162907579003880220844686222148696041857432602133894827753998572080650383305777912447151917272483538029469449...
output:
27
result:
ok 1 number(s): "27"
Test #3:
score: 0
Accepted
time: 850ms
memory: 711396kb
input:
5187 2640352926124261912741724778991366987330659389621881876017670644497364093930668042530271338851702874394631009332660937266680740235862107353443518003194307853104942996827176097428402408674756368623972812842571069642405111849826172879369776309763468485788964245903781380419155348915131587410703749...
output:
6073
result:
ok 1 number(s): "6073"
Test #4:
score: 0
Accepted
time: 544ms
memory: 703288kb
input:
200000 2 2 2 2 1 2 1 1 2 2 1 1 1 2 2 1 1 2 1 1 2 2 1 2 2 2 1 1 1 1 2 2 1 2 1 2 1 1 2 2 1 1 1 2 1 1 2 1 2 2 2 2 1 2 2 1 1 1 2 1 1 1 1 1 2 1 2 2 1 1 1 2 2 2 1 1 2 1 1 2 1 2 1 1 1 2 2 2 1 1 1 1 2 1 2 1 1 2 2 1 1 2 1 1 2 1 2 2 1 2 1 2 2 1 1 2 1 1 1 2 2 2 1 2 2 1 1 2 2 2 2 1 2 1 1 2 1 2 2 1 1 1 1 2 2 2 2...
output:
15003749259
result:
ok 1 number(s): "15003749259"
Test #5:
score: 0
Accepted
time: 2419ms
memory: 737688kb
input:
200000 944176313232170622314 2590599414036674999101 753315073608896000424 9299685298577430049245 9361800333778142620806 8988699166328904060999 9606920674025578304023 4203331868598952026136 5183047027116137697788 3968714342776915029801 8130984095583566992354 3206443643596048048798 6248561214283254355...
output:
0
result:
ok 1 number(s): "0"
Test #6:
score: 0
Accepted
time: 643ms
memory: 712540kb
input:
200000 9 10 3 5 9 3 3 9 8 5 1 2 7 8 4 6 2 3 3 9 5 5 4 9 7 5 8 2 6 10 9 7 2 2 1 10 10 6 10 7 4 7 9 7 2 2 10 4 5 8 2 2 5 8 9 5 3 9 2 1 7 6 8 8 6 3 8 2 2 9 10 2 9 7 1 9 1 4 5 9 2 7 10 1 8 7 4 8 1 10 6 4 4 9 1 9 7 3 6 5 6 9 5 3 6 6 4 4 6 1 8 6 10 3 10 2 1 4 1 4 8 2 9 1 4 8 10 8 2 2 3 6 4 7 10 10 9 4 7 6...
output:
4388485679
result:
ok 1 number(s): "4388485679"
Test #7:
score: 0
Accepted
time: 2294ms
memory: 734424kb
input:
200000 6828421000391895 1989111434563275 5896525738540342 7580233289915833 7220157112714422 6690072177484914 6664449707566084 8245839001391019 3008772159581769 8148007474169818 9400853099859484 6346860654847919 7403109176990407 2581313740335401 1273038733901266 9824983373567665 7206452987542085 7181...
output:
0
result:
ok 1 number(s): "0"
Test #8:
score: 0
Accepted
time: 1335ms
memory: 728252kb
input:
200000 163414517 35065810 104946881 686842158 509604537 114869915 194658958 55736013 211143419 526188788 18298540 311113507 727676120 517103071 25044427 38567543 386683792 246028194 750300322 4412101 865997254 674545866 775054146 977862574 699213474 347544102 740489922 632436817 297903184 435135324 ...
output:
59
result:
ok 1 number(s): "59"
Test #9:
score: 0
Accepted
time: 757ms
memory: 717900kb
input:
2 2088564186870382794642016448725374479500907752342156600368614861600912666885211013490310624029649329209019866849808883315545780833167257516031795949145341911463438482795792374909577113387320732207052482556858037878075154734524317145645776084240387870219160545328462016106959746495953786767421892196...
output:
1
result:
ok 1 number(s): "1"
Test #10:
score: 0
Accepted
time: 600ms
memory: 706172kb
input:
200000 6 1 3 9 1 8 9 9 2 6 8 6 2 3 9 2 2 7 4 7 8 8 4 8 2 7 8 9 2 9 2 4 4 1 10 6 2 10 2 6 8 3 10 3 6 10 10 10 2 4 6 4 7 8 1 2 1 1 4 10 5 5 4 10 3 8 5 6 1 7 8 1 2 6 3 8 9 9 5 1 9 5 6 10 9 4 1 7 8 3 10 4 3 2 7 7 9 4 5 6 6 7 8 10 6 6 3 6 8 1 7 4 2 6 10 8 4 2 7 4 2 5 4 9 10 5 2 3 2 4 8 7 9 7 7 8 2 5 7 2 ...
output:
4400854684
result:
ok 1 number(s): "4400854684"
Test #11:
score: 0
Accepted
time: 2246ms
memory: 731204kb
input:
200000 3118333850638 35270102833223 62994441325054 21050207685515 79452732606523 43405025574846 14676822470608 40589739145551 72610266245240 95906978427970 59399311725881 80286412880911 98171197939601 15555757959003 68766133429050 11529744877477 36884730947747 93994258932707 21245575958503 287958909...
output:
0
result:
ok 1 number(s): "0"
Test #12:
score: 0
Accepted
time: 1230ms
memory: 728208kb
input:
200000 1218982 621720 5848120 1753415 5889366 1747270 7735728 8089704 4279399 7927020 9269797 1332511 6334797 8964092 9525679 7325470 1527918 893049 8483303 1134021 8872739 532622 8977450 4503590 6512507 4903981 4892296 6522908 9237430 2297267 8063244 1546378 5054973 8702942 4392067 7868582 2029729 ...
output:
5695
result:
ok 1 number(s): "5695"
Test #13:
score: 0
Accepted
time: 720ms
memory: 717884kb
input:
2 2088564186870382794642016448725374479500907752342156600368614861600912666885211013490310624029649329209019866849808883315545780833167257516031795949145341911463438482795792374909577113387320732207052482556858037878075154734524317145645776084240387870219160545328462016106959746495953786767421892196...
output:
0
result:
ok 1 number(s): "0"
Test #14:
score: 0
Accepted
time: 815ms
memory: 714208kb
input:
7 1337338011484742791299410909385691591046809197321138600848517667449672944525104556519885455609314839827342014896149347803816156838828377155724440687227582622225528496005639283622580269360626125544811511998701746678193286138664078007880894120371020695543061391758951301196457121332483784041873539166...
output:
3
result:
ok 1 number(s): "3"
Test #15:
score: 0
Accepted
time: 812ms
memory: 710720kb
input:
274 36199225654659696764078634911736913237817300779619275513532816361663892134832409526194170532894366762053993742963156407869241123825595148459428450874407641181641292360313933002704706339921470798414371554709977458935038423965022899542511184991008496997550268720067992926078576871685757638601127765...
output:
273
result:
ok 1 number(s): "273"
Test #16:
score: 0
Accepted
time: 760ms
memory: 718896kb
input:
200000 4 3 8 5 8 9 4 10 1 3 7 1 3 10 1 10 10 7 8 2 8 9 6 6 1 2 2 6 6 7 10 7 1 3 6 2 8 4 3 3 8 9 4 3 9 6 4 1 6 3 3 5 4 2 3 9 3 3 6 7 6 1 5 5 2 10 2 1 5 9 6 7 3 2 9 1 3 8 8 3 10 7 5 5 6 9 10 8 1 5 6 2 1 8 5 4 1 7 9 9 2 8 9 8 5 7 4 9 3 3 4 7 9 1 8 1 5 9 8 8 7 10 1 4 2 3 7 8 6 1 10 10 8 9 4 10 4 5 5 6 9...
output:
4387062637
result:
ok 1 number(s): "4387062637"
Test #17:
score: 0
Accepted
time: 2383ms
memory: 737596kb
input:
200000 8244945625103564139 31587720380738895055 95764870267791202443 90342450187757930095 57990438361916446378 37041843791326956160 92044245094014254241 52147231507776742459 57440162490738372914 75951472709544205529 91095641579841704038 6354859395638708014 13171197741013485755 31875767906879519150 2...
output:
0
result:
ok 1 number(s): "0"
Test #18:
score: 0
Accepted
time: 300ms
memory: 691336kb
input:
10 6 8 6 6 7 6 3 3 2 6
output:
12
result:
ok 1 number(s): "12"
Test #19:
score: 0
Accepted
time: 741ms
memory: 717896kb
input:
2 2088564186870382794642016448725374479500907752342156600368614861600912666885211013490310624029649329209019866849808883315545780833167257516031795949145341911463438482795792374909577113387320732207052482556858037878075154734524317145645776084240387870219160545328462016106959746495953786767421892196...
output:
0
result:
ok 1 number(s): "0"
Test #20:
score: 0
Accepted
time: 2060ms
memory: 731076kb
input:
200000 51732486464 15203118134 55665354475 37097810807 44823788729 92577384010 20189320156 62707564695 81665154265 89603063623 48003727587 14457078372 37230540002 65288477498 52282695470 76070393338 26054936545 14171092817 61770329497 85319218123 57730830347 20295186479 9036398880 63607160628 825711...
output:
1
result:
ok 1 number(s): "1"
Test #21:
score: 0
Accepted
time: 362ms
memory: 691188kb
input:
1000 7 2 6 10 8 6 1 4 5 4 8 6 9 4 1 5 1 5 2 10 6 8 10 10 1 3 4 2 10 1 9 2 7 6 7 9 10 6 9 8 3 2 10 7 6 5 4 3 1 10 5 3 5 1 8 6 5 10 5 7 10 4 9 1 10 9 4 8 8 7 8 5 9 1 5 6 2 10 1 10 9 10 10 10 1 5 3 10 10 3 3 9 10 3 9 1 5 7 6 5 2 9 7 9 10 4 9 1 7 7 5 8 10 8 8 5 5 6 1 5 5 6 10 2 1 1 2 5 9 5 3 5 6 8 5 3 8...
output:
108128
result:
ok 1 number(s): "108128"
Test #22:
score: 0
Accepted
time: 1673ms
memory: 727632kb
input:
170297 36618903089511909212027904 295898671290484359833820549055 855922209609024693421257591054 104046893712788281969810034913 294974348216094859258128389147 898675289823399842963411259541 849917444544425201790051381287 554091687601993279655091754543 100543835187751461953816001432 324625661878684349...
output:
669637
result:
ok 1 number(s): "669637"
Test #23:
score: 0
Accepted
time: 837ms
memory: 717376kb
input:
9 1554055664340235444670436446744662342403532554270354440324316254234564540613440405260344004460144314614345467104554712624142524427154124266304046362254623626323466324132625200314136012323044624260020307414632254233433163613166424734133322715601644464634614352434441422431546266431240655123113002704...
output:
0
result:
ok 1 number(s): "0"
Test #24:
score: 0
Accepted
time: 312ms
memory: 691144kb
input:
30 173224810532175 17167616931584 361 605 17167680176960 956658780060 4052737359577 497497353099204 1548072001901 190392490708530 789347852872433 5 804010804445736 139520616464 43988911432793 4052739537276 514224 2178304 25273161431631 53314112869 17114366064696 20097096794 26821231255228 4944012745...
output:
29
result:
ok 1 number(s): "29"
Test #25:
score: 0
Accepted
time: 803ms
memory: 710632kb
input:
100 11549310117176145486225764017375125851223984720694884717797775426631366931455266419214045399503089615971818090352858567015012529938870819767662704737995190471260542479965705803468920094883954929878415301662741322840828368641397254767329039284292920968364857914289821588505056486091849012400101879...
output:
36
result:
ok 1 number(s): "36"
Test #26:
score: 0
Accepted
time: 1498ms
memory: 725204kb
input:
100223 94009034043768394308211497706411911232935573312371 90700235808140495519523074128684120917303691406421 72874906060637684247409916135076680433361225881761 80161826274205256086415063126094978143520789283159 98145703778166390989463238108464755254200147417281 70995217131009339533392756476859088949...
output:
0
result:
ok 1 number(s): "0"
Test #27:
score: 0
Accepted
time: 292ms
memory: 691372kb
input:
6 50 8 8 5 72 354224848179261915070
output:
4
result:
ok 1 number(s): "4"
Test #28:
score: 0
Accepted
time: 832ms
memory: 711292kb
input:
3161 7 14 130 1467 16244 105149 1241120 13689232 151890909 1684420994 10901848031 128682014414 1419326741506 15748353436059 101920677024935 1203048867903722 13269285156772499 147231358659594589 1632748057345119600 10567412357776757138 124734439986929988911 1375786096219966094366 15265241654400597567...
output:
3160
result:
ok 1 number(s): "3160"
Test #29:
score: 0
Accepted
time: 1622ms
memory: 728340kb
input:
200000 7930099016 7136448262 4599143849 4725192685 4685680672 739140078 7214691825 5031750793 4820916507 6017675339 485443032 2327198454 8808146518 7746012012 713572475 4706110510 3560774990 7482541413 8975601524 3896030632 3018545943 7048325939 2370597692 7867568189 6902951191 333917381 112842576 9...
output:
7
result:
ok 1 number(s): "7"
Test #30:
score: 0
Accepted
time: 407ms
memory: 694572kb
input:
60123 4 3 4 7 5 7 5 1 2 6 9 10 7 4 2 1 8 6 4 6 4 2 8 6 2 8 5 4 5 7 1 10 7 5 1 9 7 4 8 8 8 5 2 6 8 4 6 4 9 7 3 9 5 6 2 8 10 2 10 2 1 4 9 5 10 9 7 2 1 9 3 9 10 1 8 7 6 5 7 1 4 10 5 9 8 10 4 10 4 9 3 7 4 4 10 4 1 7 4 10 4 9 10 2 2 8 3 7 1 1 6 4 10 9 9 4 8 3 4 7 5 7 6 10 10 2 8 1 8 10 6 9 4 7 3 8 2 5 6 ...
output:
399686351
result:
ok 1 number(s): "399686351"
Test #31:
score: 0
Accepted
time: 298ms
memory: 691144kb
input:
20 11142320330634256153203413422244004724022423010341634226101444226235404243251 1510233372263004374041444256322353356243032432623343544033530634305504714430614564334410564323262245 3315442551434205740422347432544540327016564444656542244600440525402604662333366 53153452623340724302644316423336472713...
output:
0
result:
ok 1 number(s): "0"
Test #32:
score: 0
Accepted
time: 304ms
memory: 691376kb
input:
15 9227465 832040 701408733 2178309 267914296 433494437 165580141 1346269 5702887 3524578 102334155 24157817 14930352 63245986 39088169
output:
14
result:
ok 1 number(s): "14"
Test #33:
score: 0
Accepted
time: 447ms
memory: 696340kb
input:
10011 5327909559109070794570420158512927656597532686406620479564191583982981578330651724849734045529811497 9659152635523321620063357842120653540264735554377366787893904211734024058449827205523008852363337860 74727969709789190305111991663528709940303307406256850364862896747520682645094217166643105732...
output:
0
result:
ok 1 number(s): "0"
Test #34:
score: 0
Accepted
time: 878ms
memory: 711476kb
input:
10051 63063334260332707210045601560460743222655443603043556526226343270234640534370464564114515210165526527443654044521634373434642424304154632545440427364312534131536671541443033313334224226302334143144172200431314323334240461563243422303322351122343066463334623434 625665325411647124616714317265541...
output:
14
result:
ok 1 number(s): "14"
Test #35:
score: 0
Accepted
time: 2217ms
memory: 731416kb
input:
200000 3231427058997 5671035772108 505876205893 9869979702346 336233080766 4805367039084 270125613380 929924360332 6390838551951 1896341268898 3923051450784 397979630166 6527843499305 1937207519921 9355189911971 953387547771 5307619807657 6689006266290 517624961010 1532034993156 1921439567851 331239...
output:
0
result:
ok 1 number(s): "0"
Test #36:
score: 0
Accepted
time: 827ms
memory: 711468kb
input:
30 167491015938836604073444715975948275020752570351918554475806772549228015468626967999929915531115950274814727218152384400389926950026165552262394643249255747252904223055992443689134599380405599101636105379410012227917206510976118633243994494607279010051579617303878166798657109212106136099974387457...
output:
29
result:
ok 1 number(s): "29"
Test #37:
score: 0
Accepted
time: 1113ms
memory: 712776kb
input:
200000 31520 9835 67679 91981 37157 27950 36846 70635 13880 18818 52443 46788 38014 56271 48270 28452 36146 82523 60850 55346 16869 95814 89245 98640 40746 68625 53391 63023 4402 36521 95532 52344 24072 70060 11619 12227 98964 78211 95010 83216 22122 46697 31271 85556 57237 82689 92115 88247 9186 85...
output:
555586
result:
ok 1 number(s): "555586"
Test #38:
score: 0
Accepted
time: 719ms
memory: 717880kb
input:
2 7471143542670631923583760838674866685142093708045228091216520373087113961892117195149240140968159205634006625906479367372855893882103887377565868731323681755476477285090435798416695243644387513257156317699123267511524797133211810893688279220755514610253525742595752854587254548452737426517576583616...
output:
1
result:
ok 1 number(s): "1"
Test #39:
score: 0
Accepted
time: 410ms
memory: 695844kb
input:
80000 6 4 5 5 4 5 9 8 5 6 2 2 1 10 6 9 4 10 6 5 3 4 3 3 4 5 10 2 6 4 6 2 6 2 4 7 9 6 6 8 1 1 7 10 10 2 7 2 2 9 8 5 4 9 1 5 7 4 7 7 6 7 7 9 8 9 9 4 10 7 2 9 9 9 4 2 8 4 9 1 3 9 1 4 2 1 2 4 3 2 1 10 5 7 10 5 9 3 6 3 4 4 1 8 1 8 10 8 6 6 2 5 1 3 6 8 2 2 10 6 6 3 2 6 3 8 4 10 8 10 3 9 9 2 8 8 10 4 5 5 7...
output:
706251650
result:
ok 1 number(s): "706251650"
Test #40:
score: 0
Accepted
time: 780ms
memory: 718968kb
input:
200000 9 1 4 4 5 2 4 9 7 5 3 6 6 8 4 7 2 1 9 10 8 2 1 4 9 3 10 8 1 5 5 8 2 9 3 1 9 3 9 4 9 10 4 5 4 4 2 1 1 7 5 7 7 3 6 8 10 6 4 1 5 2 5 5 9 4 10 2 10 7 9 5 2 7 4 9 7 5 2 1 4 7 6 7 10 9 10 2 10 4 9 1 7 5 7 3 1 4 5 2 6 6 2 4 8 8 7 9 10 4 10 2 1 10 10 5 10 1 1 6 7 8 8 7 5 8 3 8 1 1 10 8 9 10 7 3 8 6 4...
output:
4417250451
result:
ok 1 number(s): "4417250451"
Test #41:
score: 0
Accepted
time: 1201ms
memory: 719672kb
input:
84752 86009844223237105273313186367406421847273312848013100091343 340516459610995530579473198046278412250343444815876655725270 62236463822700922600990709332929319814536375509143833251557 5611500219672931601067284378715174151735452175901717138530 64201778346042476353565735947990316834224189505881 609...
output:
420579
result:
ok 1 number(s): "420579"
Test #42:
score: 0
Accepted
time: 2354ms
memory: 737408kb
input:
200000 7127173784651987052 4249291679502906721 9703708230592019478 4404701921242244700 2344941043578422215 3091914365064271594 9867051863259427168 9880844309023770200 7211977710785226267 1694381065563438860 201683809955321192 4085536489000602058 7553409623903962290 4033981640350364868 54455660173955...
output:
0
result:
ok 1 number(s): "0"
Test #43:
score: 0
Accepted
time: 847ms
memory: 721684kb
input:
200000 9 9 2 10 3 4 3 9 7 7 8 5 9 9 7 5 8 5 7 1 5 6 3 2 7 5 7 7 2 9 8 6 2 1 8 1 3 4 10 2 3 4 4 7 4 10 8 6 1 5 3 3 3 5 5 8 6 9 3 6 5 4 2 8 10 9 1 5 1 4 8 9 4 3 4 9 10 3 6 2 10 3 3 6 6 7 4 9 5 2 1 8 8 7 308061521170126 7 4 6 1 9 3 9 9 3 1 10 8 7 2 9 10 6 2 6 10 8 5 1 5 1 7 9 5 3 6 1 4 2 6 2 8 5 3 1 6 ...
output:
4397248166
result:
ok 1 number(s): "4397248166"
Test #44:
score: 0
Accepted
time: 485ms
memory: 696864kb
input:
156 18459619692692557705784877669569448552986613407875981372394172107449477143544507182981317111359110933094916231296859516709399078435198069511763391151449973008095601542066128297192521457018669738382503324519683244087838172215626103362576668917140635977557324975206273718561053735845026938082217687...
output:
155
result:
ok 1 number(s): "155"
Test #45:
score: 0
Accepted
time: 781ms
memory: 719112kb
input:
200000 1 10 4 3 10 1 9 5 9 4 9 1 6 6 1 7 2 1 10 3 2 3 4 7 7 3 9 9 10 3 4 10 10 7 7 2 5 10 9 6 8 1 4 4 5 8 8 6 5 10 10 9 10 9 5 1 7 6 5 10 2 4 1 7 10 6 7 8 2 3 3 10 1 7 6 10 2 7 1 9 6 10 8 4 7 3 9 1 6 9 2 3 4 8 7 8 3 6 4 10 2 2 1 9 7 2 2 8 2 1 2 10 5 4 10 9 9 7 9 4 3 10 9 1 2 9 9 2 7 1 6 7 10 6 5 9 6...
output:
4407433502
result:
ok 1 number(s): "4407433502"
Test #46:
score: 0
Accepted
time: 1080ms
memory: 717040kb
input:
51002 376123568879569384290612536925367837315702704676220875375604948366932308891841579226324979782110 28623980260058260408921525210046136035459718869538444006842678034295486291710095655185249062457587 21690449377523978494384257361181223226054780834691728496618681724478608654823982012150023238151530...
output:
81486
result:
ok 1 number(s): "81486"
Test #47:
score: 0
Accepted
time: 2327ms
memory: 734412kb
input:
200000 478606336755874083 603529542039676573 240066379679942455 20635508638460497 945472883349378253 395868479387568634 865948317871000880 136079313625171264 764680881358360622 195117422398549932 143437863196805305 907507515211279442 723479709912499971 671617918537158715 439287855279754360 202716825...
output:
0
result:
ok 1 number(s): "0"
Test #48:
score: 0
Accepted
time: 810ms
memory: 713264kb
input:
19 114661534643152246311744033174352334643324503262044605562234546544736534426056314403004340112331342520053464440541422433562206354434233744572233143044234304056542423441346156352252422334142225474302135741207345424432300443162054415443457163346015613444533444074633135446264371437171714063445404655...
output:
0
result:
ok 1 number(s): "0"
Test #49:
score: 0
Accepted
time: 2163ms
memory: 731284kb
input:
200000 497856383454 506720870857 899176487457 12145678485 541966940864 272264831455 178825186059 7038707436 481602633783 181735126537 559631305498 335603421321 761406732158 369431205173 615437274239 923671138603 543441698085 733638673698 858564208935 726626729204 880133143653 415511404815 9211110013...
output:
1
result:
ok 1 number(s): "1"
Test #50:
score: 0
Accepted
time: 798ms
memory: 718072kb
input:
5 2011068126132617886949194530211424837999019187297342375967282498616949073685995418305378991927261698758022155241855161670361072821581948280878066032787805987660111096801265330758292151243775781982581126595354464038574958455139626266660161003165949122588221798586300395825356961553839057885407409810...
output:
4
result:
ok 1 number(s): "4"
Test #51:
score: 0
Accepted
time: 614ms
memory: 703196kb
input:
200000 91 67 28 7 87 97 87 80 71 5 67 1 98 85 60 62 99 46 9 81 10 7 15 91 74 69 11 34 85 47 56 48 29 16 25 5 46 9 73 24 84 10 97 22 78 18 29 70 92 98 61 43 54 66 55 15 77 20 25 16 84 11 93 65 61 91 18 59 31 93 53 33 34 59 90 41 21 27 82 49 33 64 96 18 46 71 94 95 30 62 47 9 62 79 29 28 65 67 32 48 9...
output:
591328867
result:
ok 1 number(s): "591328867"
Extra Test:
score: 0
Extra Test Passed