問題概要
$N$ 項からなる整数列 $\{ A_i \}$ が与えられる．$\prod A$ を求めよ．ただし，値が $10^{ 18 }$ を超える場合は，代わりに $-1$ を出力せよ．
制約
- $2 \leq N \leq 10^5$
- $0 \leq A_i \leq 10^{ 18 }$
解法
まず，$A$ の積は，最大で $10^6$ 桁程度になりえます．多倍長整数を使い，かつ，整数同士の積を桁数の線形時間で計算できたとしても*1 TLE します．
そこで，最終結果が $10^{ 18 }$ を超えることが計算途中で明らかになったとき，その場で計算を打ち切るようにして TLE を回避します．ただし $0$ には注意が必要で，$A_i = 0$ となる要素があれば，途中でどんなに大きな値が出てきても，最終結果は必ず $0$ になるので，先に処理するなどする必要があります．予め入力をソートすると，ソートする分遅くなりますが $0$ が先頭に来てくれることで統一的に扱うことができるようになります．
実装については，多倍長整数や 128 bit 整数の有無でやや何度に差があって，$10^{ 18 } \times 10^{ 18 }$ ぐらいの数をそのまま扱えると楽です．また，計算を打ち切るという部分については，Haskell ならば Maybe モナドで書くと楽でした．
コード
readIntegers = map ( fst . fromJust . B.readInteger ) . B.words <$> B.getLine main = getLine >> readIntegers >>= print . fromMaybe (-1) . foldM f 1 f a b | a * b <= 10 ^ 18 = Just $ a * b | otherwise = Nothing
*1:できなかった気がする
