Submission #576242

---

Source Code Expand

import qualified Data.IntMap.Strict as M
import Data.List (isPrefixOf)
import Control.Applicative
import Control.Monad

candidates :: [Int] -> String -> M.IntMap String -> [M.IntMap String]
candidates [] [] m = [m]
candidates (d:ds) str m = case M.lookup d m of
  Just g
    | isPrefixOf g str -> candidates ds (drop (length g) str) m
    | otherwise -> []
  Nothing -> do
    n <- [1..min (length str) 3]
    candidates ds (drop n str) $ M.insert d (take n str) m
candidates [] _ _ = []

solve :: [([Int], String)] -> M.IntMap String -> [M.IntMap String]
solve ((ds,str): samples) m = candidates ds str m >>= solve samples
solve [] m = [m]

main = do
  [_, n] <- map read <$> words <$> getLine
  let smp [v, w] = (map (subtract (fromEnum '0') . fromEnum) v, w)
  samples <- map (smp . words) <$> replicateM n getLine
  putStr $ unlines $ M.elems $ head $ solve samples M.empty

Submission Info

Judge Result