結果

問題 No.2 素因数ゲーム
ユーザー poapoapoapoa
提出日時 2020-07-23 23:31:42
言語 Haskell
(9.8.2)
結果
AC  
実行時間 4 ms / 5,000 ms
コード長 3,706 bytes
コンパイル時間 2,862 ms
コンパイル使用メモリ 177,492 KB
実行使用メモリ 8,164 KB
最終ジャッジ日時 2023-09-06 03:49:18
合計ジャッジ時間 4,761 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 3 ms
6,932 KB
testcase_01 AC 3 ms
6,900 KB
testcase_02 AC 2 ms
6,968 KB
testcase_03 AC 2 ms
6,984 KB
testcase_04 AC 2 ms
6,972 KB
testcase_05 AC 3 ms
6,992 KB
testcase_06 AC 3 ms
7,000 KB
testcase_07 AC 2 ms
7,044 KB
testcase_08 AC 3 ms
7,140 KB
testcase_09 AC 2 ms
6,976 KB
testcase_10 AC 3 ms
7,000 KB
testcase_11 AC 3 ms
7,040 KB
testcase_12 AC 2 ms
7,000 KB
testcase_13 AC 2 ms
6,980 KB
testcase_14 AC 3 ms
7,000 KB
testcase_15 AC 3 ms
7,292 KB
testcase_16 AC 3 ms
7,136 KB
testcase_17 AC 2 ms
7,056 KB
testcase_18 AC 2 ms
6,968 KB
testcase_19 AC 3 ms
7,868 KB
testcase_20 AC 3 ms
7,708 KB
testcase_21 AC 4 ms
8,164 KB
testcase_22 AC 2 ms
7,164 KB
testcase_23 AC 3 ms
7,040 KB
testcase_24 AC 3 ms
7,176 KB
testcase_25 AC 3 ms
7,192 KB
testcase_26 AC 3 ms
7,016 KB
testcase_27 AC 3 ms
6,944 KB
testcase_28 AC 3 ms
7,016 KB
testcase_29 AC 3 ms
7,000 KB
testcase_30 AC 3 ms
7,488 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
Loaded package environment from /home/judge/.ghc/x86_64-linux-9.6.1/environments/default
[1 of 2] Compiling Main             ( Main.hs, Main.o )
[2 of 2] Linking a.out

ソースコード

diff # 

import qualified Data.Bits           as Bits
import qualified Data.List           as List
-------------------------------------------------------------------------------
-- primes
-------------------------------------------------------------------------------
spin :: Num int => int -> [int] -> [int]
spin x (y:ys) = x : spin (x+y) ys

type Wheel int      = ([int], [int])
data Queue int
  = Empty
  | Fork [int] [Queue int]
type Composites int = (Queue int, [[int]])

enqueue :: Ord int => [int] -> Queue int -> Queue int
enqueue ns = merge (Fork ns [])

mergeAll :: Ord int => [Queue int] -> Queue int
mergeAll []       = Empty
mergeAll [x]      = x
mergeAll (x:y:qs) = merge (merge x y) (mergeAll qs)

dequeue :: Ord int => Queue int -> ([int], Queue int)
dequeue (Fork ns qs) = (ns, mergeAll qs)

merge :: Ord int => Queue int -> Queue int -> Queue int
merge Empty y    = y
merge x Empty    = x
merge 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)

discard :: Ord int => int -> Composites int -> Composites int
discard n ns
  | n == m    = discard n ms
  | otherwise = ns
  where
    (m, ms) = splitComposites ns

splitComposites :: Ord int => Composites int -> (int, Composites int)
splitComposites (Empty, xs:xss) = splitComposites (Fork xs [], xss)
splitComposites (queue, xss@((x:xs):yss))
  | x < z     = (x, discard x (enqueue xs queue, yss))
  | otherwise = (z, discard z (enqueue zs queue', xss))
  where
    (z:zs, queue') = dequeue queue

sieveComps :: (Ord int, Num int) => int -> [int] -> Composites int -> [[int]]
sieveComps cand ns@(m:ms) xs
  | cand == comp = sieveComps (cand+m) ms ys
  | cand <  comp = spin cand ns : sieveComps (cand + m) ms xs
  | otherwise    = sieveComps cand ns ys
  where
    (comp, ys) = splitComposites xs

composites :: (Ord int, Num int) => int -> [int] -> Composites int
composites p ns = (Empty, map comps (spin p ns: sieve p ns))
  where
    comps xs@(x:_) = map (x*) xs

sieve :: (Ord int, Num int) => int -> [int] -> [[int]]
sieve p ns@(m:ms) = spin p ns : sieveComps (p+m) ms (composites p ns)

cancel :: Integral int => int -> int -> int -> [int] -> [int]
cancel 0 _ _ _ = []
cancel m p n (x:ys@(y:zs))
  | nx `mod` p > 0 = x : cancel (m - x) p nx ys
  | otherwise      = cancel m p n (x+y:zs)
  where
    nx = n + x

next :: Integral int => Wheel int -> Wheel int
next (ps@(p:_), xs) = (py:ps, cancel (product ps) p py ys)
  where
    (y:ys) = cycle xs
    py = p + y

wheel :: Integral int => Int -> Wheel int
wheel n = iterate next ([2], [1]) !! n
---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ----
  ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ----
wheelSieve :: Integral int => Int -> [int]
wheelSieve k = reverse ps ++ map head (sieve p (cycle ns))
  where
    (p:ps,ns) = wheel k

primeFactors :: Integral int => int -> [int]
primeFactors n = factors n (wheelSieve 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 = wheelSieve 6

isPrime :: Integral int => int -> Bool
isPrime n
  | n > 1 = primeFactors n == [n]
  | otherwise = False

-------------------------------------------------------------------------------
-- primes
-------------------------------------------------------------------------------

main :: IO ()
main = do
  n <- readLn :: IO Int
  if (solve n) == 0
    then putStrLn "Bob"
    else putStrLn "Alice"

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