#545913 (Haskell) No.2 素因数ゲーム

• 問題: No.2 素因数ゲーム
• ユーザー: かりあげクン
• 提出日時: 2020-09-02 05:17:51
• 言語: Haskell (9.8.2)
• 結果: CE (最新)
  AC
  (最初)
• 実行時間: -
• コード長: 6,400 bytes
• コンパイル時間: 294 ms
• コンパイル使用メモリ: 169,856 KB
• 最終ジャッジ日時: 2024-11-14 23:48:27
• 合計ジャッジ時間: 655 ms
• ジャッジサーバーID （参考情報）: judge1 / judge2

コンパイルメッセージ

Loaded package environment from /home/judge/.ghc/x86_64-linux-9.8.2/environments/default

Main.hs:9:28: warning: [GHC-53692] [-Wdeprecated-flags]
    -XTypeInType is deprecated: use -XDataKinds and -XPolyKinds instead
  |
9 | {-# LANGUAGE TypeFamilies, TypeInType, UnboxedTuples, ViewPatterns  #-}
  |                            ^^^^^^^^^^
[1 of 2] Compiling Main             ( Main.hs, Main.o )

Main.hs:44:1: error: [GHC-61948]
    Could not find module ‘Data.ByteString.Lazy.Builder’.
    Perhaps you meant
      Data.ByteString.Builder (from bytestring-0.12.1.0)
      Data.ByteString.Lazy.Char8 (from bytestring-0.12.1.0)
      Data.ByteString.Lazy.ReadInt
    Use -v to see a list of the files searched for.
   |
44 | import qualified Data.ByteString.Lazy.Builder  as BSLB
   | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

Main.hs:48:1: error: [GHC-87110]
    Could not load module ‘Data.Graph’.
    It is a member of the hidden package ‘containers-0.6.8’.
    Use -v to see a list of the files searched for.
   |
48 | import qualified Data.Graph                    as Graph
   | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

Main.hs:49:1: error: [GHC-87110]
    Could not load module ‘Data.IntMap’.
    It is a member of the hidden package ‘containers-0.6.8’.
    Use -v to see a list of the files searched for.
   |
49 | import           Data.IntMap                   (IntMap)
   | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

Main.hs:50:1: error: [GHC-87110]
    Could not load module ‘Data.IntMap’.
    It is a member of the hidden package ‘containers-0.6.8’.
    Use -v to see a list of the files searched for.
   |
50 | import qualified Data.IntMap                   as IntMap
   | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

Main.hs:51:1: error: [GHC-87110]
    Could not load module ‘Data.IntSet’.
    It is a member of the hidden package ‘containers-0.6.8’.
    Use -v to see a list of the files searc

ソースコード

{-# LANGUAGE DeriveFunctor                                          #-}
{-# LANGUAGE BangPatterns, BinaryLiterals, CPP, DerivingStrategies  #-}
{-# LANGUAGE DerivingVia, FlexibleContexts, FlexibleInstances       #-}
{-# LANGUAGE GeneralizedNewtypeDeriving, KindSignatures, LambdaCase #-}
{-# LANGUAGE MagicHash, MultiParamTypeClasses, MultiWayIf           #-}
{-# LANGUAGE NumericUnderscores, OverloadedStrings, PatternSynonyms #-}
{-# LANGUAGE RankNTypes, RecordWildCards, ScopedTypeVariables       #-}
{-# LANGUAGE StandaloneDeriving, TupleSections, TypeApplications    #-}
{-# LANGUAGE TypeFamilies, TypeInType, UnboxedTuples, ViewPatterns  #-}

{- base -}
import           Control.Applicative
import qualified Control.Arrow                 as Arrow
import           Control.Monad
import           Control.Monad.ST
import           Data.Bits
import           Data.Bool
import           Data.Complex
import qualified Data.Char                     as Char
import qualified Data.Foldable                 as Foldable
import           Data.Function
import qualified Data.List                     as List
import           Data.Maybe
import           Data.Monoid
import           Data.Ratio
import           Data.Ord
import           Data.Semigroup
import qualified Data.Word                     as Word
import           Foreign                       hiding (void)
import           GHC.Exts
import           Unsafe.Coerce
{- array -}
import qualified Data.Array.IO                 as ArrIO
import qualified Data.Array.MArray             as ArrMA
import qualified Data.Array.ST                 as ArrST
import qualified Data.Array.Storable           as ArrStore
import qualified Data.Array.Unboxed            as ArrU
{- bytestring -}
import qualified Data.ByteString               as BS
import qualified Data.ByteString.Builder       as BSB
import qualified Data.ByteString.Builder.Extra as BSBE
import qualified Data.ByteString.Char8         as BSC8
import qualified Data.ByteString.Lazy          as BSL
import qualified Data.ByteString.Lazy.Builder  as BSLB
import qualified Data.ByteString.Lazy.Char8    as BSLC8
import qualified Data.ByteString.Unsafe        as BSU
{- containers -}
import qualified Data.Graph                    as Graph
import           Data.IntMap                   (IntMap)
import qualified Data.IntMap                   as IntMap
import           Data.IntSet                   (IntSet)
import qualified Data.IntSet                   as IntSet
import qualified Data.Sequence                 as Seq
import qualified Data.Tree                     as Tree
{- integer-gmp -}
import           GHC.Integer.GMP.Internals
{- vector -}
import qualified Data.Vector                   as V
import qualified Data.Vector.Generic           as VG
import qualified Data.Vector.Generic.Mutable   as VGM
import qualified Data.Vector.Mutable           as VM
import qualified Data.Vector.Primitive         as VP
import qualified Data.Vector.Primitive.Mutable as VPM
import qualified Data.Vector.Unboxed           as VU
import qualified Data.Vector.Unboxed.Mutable   as VUM

-------------------------------------------------------------------------------
-- main
-------------------------------------------------------------------------------

main :: IO ()
main = readLn >>= putStrLn . bool "Alice" "Bob" . solve

solve :: Int -> Bool
solve = (== 0) . List.foldl1' xor . map length . List.group . primeFactors

pSpin :: Num int => int -> [int] -> [int]
pSpin x (y:ys) = x : pSpin (x + y) ys
type PWheel int      = ([int], [int])
data PQueue int
  = Empty
  | Fork [int] [PQueue int]
type Composites int = (PQueue int, [[int]])
pEnqueue :: Ord int => [int] -> PQueue int -> PQueue int
pEnqueue ns = pMerge (Fork ns [])
pMergeAll :: Ord int => [PQueue int] -> PQueue int
pMergeAll []       = Empty
pMergeAll [x]      = x
pMergeAll (x:y:qs) = pMerge (pMerge x y) (pMergeAll qs)
pDequeue :: Ord int => PQueue int -> ([int], PQueue int)
pDequeue (Fork ns qs) = (ns, pMergeAll qs)
pMerge :: Ord int => PQueue int -> PQueue int -> PQueue int
pMerge Empty y    = y
pMerge x Empty    = x
pMerge x y
  | prio x <= prio y = join x y
  | otherwise        = join y x
  where
    prio (Fork (n:_) _) = n
    join (Fork ns qs) q = Fork ns (q:qs)
pDiscard :: Ord int => int -> Composites int -> Composites int
pDiscard n ns
  | n == m    = pDiscard n ms
  | otherwise = ns
  where
    (m, ms) = pSplitComposites ns
pSplitComposites :: Ord int => Composites int -> (int, Composites int)
pSplitComposites (Empty, xs:xss) = pSplitComposites (Fork xs [], xss)
pSplitComposites (queue, xss@((x:xs):yss))
  | x < z     = (x, pDiscard x (pEnqueue xs queue, yss))
  | otherwise = (z, pDiscard z (pEnqueue zs queue', xss))
  where
    (z:zs, queue') = pDequeue queue
pSieveComps :: (Ord int, Num int) => int -> [int] -> Composites int -> [[int]]
pSieveComps cand ns@(m:ms) xs
  | cand == comp = pSieveComps (cand+m) ms ys
  | cand <  comp = pSpin cand ns : pSieveComps (cand + m) ms xs
  | otherwise    = pSieveComps cand ns ys
  where
    (comp, ys) = pSplitComposites xs
pComposites :: (Ord int, Num int) => int -> [int] -> Composites int
pComposites p ns = (Empty, map comps (pSpin p ns: pSieve p ns))
  where
    comps xs@(x:_) = map (x*) xs
pSieve :: (Ord int, Num int) => int -> [int] -> [[int]]
pSieve p ns@(m:ms) = pSpin p ns : pSieveComps (p+m) ms (pComposites p ns)
pCancel :: Integral int => int -> int -> int -> [int] -> [int]
pCancel 0 _ _ _ = []
pCancel m p n (x:ys@(y:zs))
  | nx `mod` p > 0 = x : pCancel (m - x) p nx ys
  | otherwise      = pCancel m p n (x+y:zs)
  where
    nx = n + x
pNext :: Integral int => PWheel int -> PWheel int
pNext (ps@(p:_), xs) = (py:ps, pCancel (product ps) p py ys)
  where
    (y:ys) = cycle xs
    py = p + y
pWheel :: Integral int => Int -> PWheel int
pWheel n = iterate pNext ([2], [1]) !! n

pWheelSieve :: Integral int => Int -> [int]
pWheelSieve k = reverse ps ++ map head (pSieve p (cycle ns))
  where
    (p:ps,ns) = pWheel k
primeFactors :: Integral int => int -> [int]
primeFactors n = factors n (pWheelSieve 6)
  where
    factors 1 _      = []
    factors m (p:ps)
      | m < p * p = [m]
      | r == 0    = p : factors q (p:ps)
      | otherwise = factors m ps
      where
        (q, r) = quotRem m p
primes :: Integral int => [int]
primes = pWheelSieve 6
isPrime :: Integral int => int -> Bool
isPrime n
  | n > 1 = primeFactors n == [n]
  | otherwise = False