結果

問題 No.7 プライムナンバーゲーム
ユーザー okadukiokaduki
提出日時 2016-05-05 00:42:29
言語 Haskell
(9.8.2)
結果
AC  
実行時間 2,384 ms / 5,000 ms
コード長 1,708 bytes
コンパイル時間 4,404 ms
コンパイル使用メモリ 174,080 KB
実行使用メモリ 12,160 KB
最終ジャッジ日時 2024-04-09 04:00:03
合計ジャッジ時間 17,723 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,820 KB
testcase_01 AC 1 ms
6,948 KB
testcase_02 AC 2,384 ms
11,904 KB
testcase_03 AC 131 ms
9,216 KB
testcase_04 AC 34 ms
8,704 KB
testcase_05 AC 33 ms
8,576 KB
testcase_06 AC 655 ms
11,008 KB
testcase_07 AC 432 ms
9,984 KB
testcase_08 AC 183 ms
9,472 KB
testcase_09 AC 1,013 ms
10,880 KB
testcase_10 AC 1 ms
6,944 KB
testcase_11 AC 436 ms
9,856 KB
testcase_12 AC 1,677 ms
12,160 KB
testcase_13 AC 1,789 ms
12,040 KB
testcase_14 AC 2,374 ms
12,160 KB
testcase_15 AC 2,247 ms
12,032 KB
testcase_16 AC 2,066 ms
12,020 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
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 = it [2..10000]
  where
    it [] = []
    it (x:xs) = (x:) $ it $ filter (\a -> a`mod`x /= 0) xs

iswin = memo f
  where
    f x | x <= 3 = False
        | otherwise =
            not $ and $ map (iswin . (\p -> x-p)) $ takeWhile (<=x-2) primes

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

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