結果

問題 No.3 ビットすごろく
ユーザー momen999
提出日時 2017-05-02 18:28:31
言語 Haskell
(9.10.1)
結果
MLE  
実行時間 -
コード長 1,069 bytes
コンパイル時間 3,217 ms
コンパイル使用メモリ 172,416 KB
実行使用メモリ 682,752 KB
最終ジャッジ日時 2024-09-14 04:44:15
合計ジャッジ時間 50,549 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge6
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 22 MLE * 11
権限があれば一括ダウンロードができます
コンパイルメッセージ
Loaded package environment from /home/judge/.ghc/x86_64-linux-9.8.2/environments/default
[1 of 2] Compiling Main             ( Main.hs, Main.o )
[2 of 2] Linking a.out

ソースコード

diff # 

import Data.Bits
import Data.Maybe

solve :: [(Int, Int)] -> [Int] -> Int -> Int
solve flag [] n = case (lookup n flag) of
    Just x ->
        x
    Nothing ->
        -1
solve flag (q:queue) n = solve flag' queue' n
    where
        qb = popCount q
        inc = q + qb
        dec = q - qb
        isInc = inc <= n && isNothing (lookup inc flag)
        isDec = dec > 0 && isNothing (lookup dec flag)
        flag'   | isInc && isDec    = flag ++ [(inc, fromJust (lookup q flag) + 1)] ++ [(dec, fromJust (lookup q flag) + 1)]
                | isInc             = flag ++ [(inc, fromJust (lookup q flag) + 1)]
                | isDec             = flag ++ [(dec, fromJust (lookup q flag) + 1)]
                | otherwise         = flag
        queue'  | isInc && isDec    = queue ++ [inc] ++ [dec]
                | isInc             = queue ++ [inc]
                | isDec             = queue ++ [dec]
                | otherwise         = queue

main = do
    --n <- (read :: String -> Int) <$> getLine
    n <- readLn
    print $ solve [(0, 0), (1, 1)] [1] n
0