Submission #898004


Source Code Expand

{-# LANGUAGE ScopedTypeVariables #-}
import Control.Applicative
import Control.Monad
import Control.Monad.State
import Control.DeepSeq
import Data.Array
import Data.Bits
import Data.Char
import Data.Functor.Identity
import Data.List
import Data.Maybe
import Data.Ord
import Data.Tree
import Data.Tuple
import qualified System.IO
import qualified Data.Map as M
import qualified Data.Set as S
import qualified Data.Sequence as Q
import qualified Data.ByteString.Char8 as B

main = do
  [n,m] <- getInts
  q <- getInt
  as <- getInts
  let goal = dropLastIncr $ lru m as
  -- print goal
  let g = S.fromList goal
  let rs = reverse $ filter (`S.member` g) as
  let result = if n * length goal > length rs
        then Nothing
        else (iterate (>>= dropGreedy goal) (Just rs)) !! n
  -- mapM_ print . take n $ iterate (>>= dropGreedy goal) (Just rs)
  putStrLn . yesNo $ isJust result

dropGreedy :: (Eq a) => [a] -> [a] -> Maybe [a]
dropGreedy [] xs = Just xs
dropGreedy _ [] = Nothing
dropGreedy (x:xs) (y:ys)
  | x == y  = dropGreedy xs ys
  | otherwise = (y :) <$> dropGreedy (x:xs) ys

lru m as = let
  lasts = accumArray min 1 (1,m) $ zip as [0,-1..]
  in  map snd . sort . map swap $ assocs lasts

dropLastIncr = reverse . foo . reverse  where
  foo xs = map snd . dropWhile (uncurry (>)) $ zip xs (tail xs)
 
type Z = Int
type Q = Rational
type R = Double
type S = String

fint :: (Integral a, Num b) => a -> b
fint = fromIntegral

getInt = fst . fromJust . B.readInt <$> B.getLine
getIntPair = (\[a,b]->(a,b)) <$> getInts
getInts = map (fst . fromJust . B.readInt) . B.words <$> B.getLine
getStr = B.unpack <$> B.getLine

yesNo :: Bool -> String
yesNo True = "Yes"
yesNo False = "No"

printList :: (Show a) => [a] -> IO ()
printList = putStrLn . unwords . map show

readLnList :: (Read a) => IO [a]
readLnList = map read . words <$> getLine


-----  Union-find
type UnionFindT v m a = StateT (M.Map v (UnionFindVal v)) m a
newtype UnionFindVal v = UnionFindVal v

runUnionFindT :: (Monad m) => UnionFindT v m a -> m a
runUnionFindT = flip evalStateT $ M.empty

runUnionFind = runIdentity . runUnionFindT

ufFresh :: (Monad m, Ord v) => v -> UnionFindT v m ()
ufFresh v = modify $ M.insert v (UnionFindVal v)

ufClass :: (Monad m, Ord v) => v -> UnionFindT v m v
ufClass v = do
  (UnionFindVal pv) <- gets (M.! v)
  if v == pv
    then return v
    else do
      c <- ufClass pv
      modify $ M.insert v (UnionFindVal c)
      return c

ufUnify v w = do
  cv <- ufClass v
  cw <- ufClass w
  modify $ M.insert cw (UnionFindVal cv)
  return $ cv /= cw

Submission Info

Submission Time
Task E - LRU Puzzle
User tos
Language Haskell (GHC 7.10.3)
Score 1200
Code Size 2660 Byte
Status AC
Exec Time 611 ms
Memory 52092 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 1200 / 1200
Status
AC × 4
AC × 76
Set Name Test Cases
Sample 0_00.txt, 0_01.txt, 0_02.txt, 0_03.txt
All 0_00.txt, 0_01.txt, 0_02.txt, 0_03.txt, 1_00.txt, 1_01.txt, 1_02.txt, 1_03.txt, 1_04.txt, 1_05.txt, 1_06.txt, 1_07.txt, 1_08.txt, 1_09.txt, 1_10.txt, 1_11.txt, 1_12.txt, 1_13.txt, 1_14.txt, 1_15.txt, 1_16.txt, 1_17.txt, 1_18.txt, 1_19.txt, 1_20.txt, 1_21.txt, 1_22.txt, 1_23.txt, 1_24.txt, 1_25.txt, 1_26.txt, 1_27.txt, 1_28.txt, 1_29.txt, 1_30.txt, 1_31.txt, 1_32.txt, 1_33.txt, 1_34.txt, 1_35.txt, 1_36.txt, 1_37.txt, 1_38.txt, 1_39.txt, 1_40.txt, 1_41.txt, 1_42.txt, 1_43.txt, 1_44.txt, 1_45.txt, 1_46.txt, 1_47.txt, 1_48.txt, 1_49.txt, 1_50.txt, 1_51.txt, 1_52.txt, 1_53.txt, 1_54.txt, 1_55.txt, 1_56.txt, 1_57.txt, 1_58.txt, 1_59.txt, 1_60.txt, 1_61.txt, 1_62.txt, 1_63.txt, 1_64.txt, 1_65.txt, 1_66.txt, 1_67.txt, 1_68.txt, 1_69.txt, 1_70.txt, 1_71.txt
Case Name Status Exec Time Memory
0_00.txt AC 3 ms 380 KB
0_01.txt AC 3 ms 380 KB
0_02.txt AC 3 ms 380 KB
0_03.txt AC 3 ms 380 KB
1_00.txt AC 3 ms 380 KB
1_01.txt AC 3 ms 380 KB
1_02.txt AC 131 ms 27004 KB
1_03.txt AC 141 ms 27004 KB
1_04.txt AC 132 ms 27004 KB
1_05.txt AC 121 ms 27004 KB
1_06.txt AC 136 ms 38268 KB
1_07.txt AC 187 ms 46460 KB
1_08.txt AC 136 ms 38268 KB
1_09.txt AC 136 ms 38268 KB
1_10.txt AC 132 ms 31100 KB
1_11.txt AC 133 ms 31100 KB
1_12.txt AC 131 ms 31100 KB
1_13.txt AC 131 ms 31100 KB
1_14.txt AC 133 ms 31100 KB
1_15.txt AC 134 ms 31100 KB
1_16.txt AC 130 ms 31100 KB
1_17.txt AC 130 ms 31100 KB
1_18.txt AC 210 ms 37244 KB
1_19.txt AC 326 ms 32124 KB
1_20.txt AC 227 ms 36220 KB
1_21.txt AC 611 ms 52092 KB
1_22.txt AC 240 ms 39292 KB
1_23.txt AC 387 ms 36220 KB
1_24.txt AC 189 ms 39932 KB
1_25.txt AC 398 ms 38268 KB
1_26.txt AC 66 ms 14716 KB
1_27.txt AC 53 ms 11644 KB
1_28.txt AC 82 ms 17788 KB
1_29.txt AC 84 ms 17788 KB
1_30.txt AC 122 ms 28028 KB
1_31.txt AC 124 ms 28028 KB
1_32.txt AC 101 ms 25980 KB
1_33.txt AC 167 ms 30076 KB
1_34.txt AC 113 ms 22908 KB
1_35.txt AC 171 ms 27004 KB
1_36.txt AC 76 ms 18812 KB
1_37.txt AC 252 ms 28028 KB
1_38.txt AC 295 ms 36220 KB
1_39.txt AC 244 ms 35196 KB
1_40.txt AC 167 ms 38652 KB
1_41.txt AC 534 ms 45436 KB
1_42.txt AC 60 ms 12668 KB
1_43.txt AC 70 ms 15740 KB
1_44.txt AC 50 ms 11644 KB
1_45.txt AC 69 ms 15740 KB
1_46.txt AC 88 ms 20604 KB
1_47.txt AC 101 ms 23932 KB
1_48.txt AC 94 ms 22908 KB
1_49.txt AC 183 ms 34172 KB
1_50.txt AC 51 ms 12668 KB
1_51.txt AC 47 ms 11644 KB
1_52.txt AC 53 ms 13692 KB
1_53.txt AC 77 ms 17916 KB
1_54.txt AC 103 ms 28924 KB
1_55.txt AC 77 ms 22908 KB
1_56.txt AC 112 ms 29052 KB
1_57.txt AC 202 ms 33148 KB
1_58.txt AC 47 ms 10620 KB
1_59.txt AC 47 ms 11644 KB
1_60.txt AC 46 ms 11644 KB
1_61.txt AC 73 ms 13692 KB
1_62.txt AC 76 ms 20860 KB
1_63.txt AC 122 ms 28540 KB
1_64.txt AC 68 ms 17788 KB
1_65.txt AC 142 ms 29052 KB
1_66.txt AC 73 ms 16764 KB
1_67.txt AC 63 ms 16892 KB
1_68.txt AC 73 ms 17788 KB
1_69.txt AC 74 ms 19836 KB
1_70.txt AC 128 ms 28028 KB
1_71.txt AC 140 ms 34172 KB