結果

問題 No.7 プライムナンバーゲーム
コンテスト
ユーザー okaduki
提出日時 2016-05-05 00:53:46
言語 Haskell
(9.10.1)
結果
AC  
実行時間 2,165 ms / 5,000 ms
コード長 1,754 bytes
コンパイル時間 8,947 ms
コンパイル使用メモリ 173,312 KB
実行使用メモリ 10,112 KB
最終ジャッジ日時 2024-10-01 15:45:10
合計ジャッジ時間 20,340 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 17
権限があれば一括ダウンロードができます
コンパイルメッセージ
Loaded package environment from /home/judge/.ghc/x86_64-linux-9.8.2/environments/default
[1 of 2] Compiling Main             ( Main.hs, Main.o )

Main.hs:31:12: warning: [GHC-63394] [-Wx-partial]
    In the use of ‘tail’
    (imported from Prelude, but defined in GHC.List):
    "This is a partial function, it throws an error on empty lists. Replace it with drop 1, or use pattern matching or Data.List.uncons instead. Consider refactoring to use Data.List.NonEmpty."
   |
31 |     bits = tail . reverse . map (`mod` 2) . takeWhile (>0) . iterate (`div` 2)
   |            ^^^^
[2 of 2] Linking a.out

ソースコード

diff # 

import Control.Applicative
import Control.Monad
import qualified Data.ByteString.Char8 as B
import Data.Maybe (fromJust)
import Text.Printf
import Debug.Trace

class MemoIx a where
  index :: a -> Integer
  unindex :: Integer -> a
instance MemoIx Integer where
  index n | n >= 0 = n*2
          | otherwise = -n*2-1
  unindex n | n `mod` 2 == 0 = n `div` 2
            | otherwise = -((n+1) `div` 2)
instance (MemoIx a, MemoIx b) => MemoIx (a,b) where
  index (a,b) = l*(l+1) `div`2 + ib
    where
      ia = index a
      ib = index b
      l = ia+ib
  unindex ix = (unindex ia, unindex ib)
    where
      l = floor ((-1 + sqrt (1+8*fromIntegral ix))/2)
      ib = ix - l*(l+1) `div` 2
      ia = l - ib
data Tree a = Tree a (Tree a) (Tree a)
findTree :: MemoIx a => Tree b -> a -> b
findTree tree ix = f (bits $ index ix + 1) tree
  where
    bits = tail . reverse . map (`mod` 2) . takeWhile (>0) . iterate (`div` 2)
    f [] (Tree v _ _) = v
    f (0:bs) (Tree _ l _) = f bs l
    f (1:bs) (Tree _ _ r) = f bs r
genTree :: MemoIx a => (a -> b) -> Tree b
genTree f = gen 0
  where
    gen i = Tree (f $ unindex i) (gen (i*2+1)) (gen (i*2+2))
memofix :: MemoIx a => ((a -> b) -> (a -> b)) -> (a -> b)
memofix f = memof where
  memof = f $ findTree tbl
  tbl = genTree memof
memo :: MemoIx a => (a -> b) -> a -> b
memo f = findTree (genTree f)

primes = 2:3:[6*i+j | i <- [1..], j <- [-1,1], isprime $ 6*i+j] where
  isprime n = null [p | p <- takeWhile (\x -> x*x<=n) primes, n `mod` p == 0]


iswin = memo f
  where
    f x | x <= 3 = False
        | otherwise =
            not $ and [b | p <- takeWhile (<=x-2) primes, let b = iswin (x-p)]

answer n = if iswin n then "Win" else "Lose"

main = do
  n <- readLn :: IO Integer
  putStrLn $ answer n
0