結果
問題 | No.506 限られたジャパリまん |
ユーザー | aimy |
提出日時 | 2017-04-29 10:35:26 |
言語 | Haskell (9.8.2) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,448 bytes |
コンパイル時間 | 5,211 ms |
コンパイル使用メモリ | 181,812 KB |
実行使用メモリ | 20,292 KB |
最終ジャッジ日時 | 2023-09-10 12:54:17 |
合計ジャッジ時間 | 7,648 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
20,292 KB |
testcase_01 | AC | 3 ms
7,280 KB |
testcase_02 | AC | 12 ms
11,344 KB |
testcase_03 | AC | 3 ms
7,248 KB |
testcase_04 | AC | 52 ms
11,736 KB |
testcase_05 | AC | 6 ms
9,352 KB |
testcase_06 | AC | 3 ms
7,532 KB |
testcase_07 | AC | 52 ms
11,772 KB |
testcase_08 | TLE | - |
testcase_09 | -- | - |
testcase_10 | -- | - |
testcase_11 | -- | - |
testcase_12 | -- | - |
testcase_13 | -- | - |
testcase_14 | -- | - |
testcase_15 | -- | - |
testcase_16 | -- | - |
testcase_17 | -- | - |
testcase_18 | -- | - |
testcase_19 | -- | - |
testcase_20 | -- | - |
testcase_21 | -- | - |
testcase_22 | -- | - |
testcase_23 | -- | - |
testcase_24 | -- | - |
コンパイルメッセージ
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
ソースコード
import Data.Tuple import Data.List import Data.Ord data Tree a = Node a (Tree a) (Tree a) memoize f = memof where memof = f (query (blank memof)) blank f = blank' 1 where blank' k = Node (f k) (blank' (2*k)) (blank' (2*k+1)) query m x = query' m bits where bits = reverse (take w (unfoldr (return . swap . flip divMod 2) x)) w = floor (logBase 2 (fromIntegral x)) query' (Node v left right) bs | bs == [] = v | head bs == 0 = query' left (tail bs) | otherwise = query' right (tail bs) combBy :: Integer -> [a] -> [[a]] combBy 0 _ = [[]] combBy _ [] = [] combBy n (x:xs) = map (x:) (combBy (n-1) xs) ++ combBy n xs main = do [h,w,k,p] <- map read . words <$> getLine xyns <- map ((\[x,y,n] -> ((read x, read y),n)) . words) . lines <$> getContents let (r,fs) = japari (h+1) (w+1) k p xyns print (mod r (10^9+7)) mapM_ putStrLn fs japari :: Integer -> Integer -> Integer -> Integer -> [((Integer,Integer),String)] -> (Integer, [String]) japari h w k p xyns = (route h w (map (pos.fst) left) 0, (map snd xyns) \\ (map snd left)) where left = maximumBy (comparing (\fs -> route h w (map (pos.fst) fs) 0)) (combBy (k-p) xyns) pos (x,y) = y*h + x route h w fs = memoize $ \f n -> if isFriend n then 0 else if isGoal n then 1 else if isNB n then f (n+1) else if isEB n then f (n+h) else f (n+1) + f (n+h) where isGoal n = n == h*w-1 isNB n = div n h == w-1 isEB n = mod n h == h-1 isFriend n = elem n fs