Submission #897873


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 = (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 2593 Byte
Status AC
Exec Time 602 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 149 ms 38268 KB
1_03.txt AC 157 ms 38268 KB
1_04.txt AC 149 ms 38268 KB
1_05.txt AC 157 ms 38268 KB
1_06.txt AC 153 ms 45180 KB
1_07.txt AC 210 ms 51580 KB
1_08.txt AC 151 ms 44540 KB
1_09.txt AC 155 ms 45180 KB
1_10.txt AC 132 ms 32124 KB
1_11.txt AC 130 ms 31100 KB
1_12.txt AC 130 ms 31100 KB
1_13.txt AC 131 ms 31100 KB
1_14.txt AC 132 ms 32124 KB
1_15.txt AC 132 ms 31100 KB
1_16.txt AC 132 ms 31100 KB
1_17.txt AC 133 ms 31100 KB
1_18.txt AC 209 ms 37244 KB
1_19.txt AC 314 ms 31100 KB
1_20.txt AC 225 ms 36220 KB
1_21.txt AC 602 ms 52092 KB
1_22.txt AC 239 ms 39292 KB
1_23.txt AC 385 ms 36220 KB
1_24.txt AC 188 ms 40316 KB
1_25.txt AC 406 ms 38268 KB
1_26.txt AC 65 ms 14716 KB
1_27.txt AC 52 ms 11260 KB
1_28.txt AC 81 ms 17788 KB
1_29.txt AC 83 ms 18812 KB
1_30.txt AC 120 ms 27004 KB
1_31.txt AC 123 ms 28028 KB
1_32.txt AC 99 ms 25980 KB
1_33.txt AC 166 ms 30076 KB
1_34.txt AC 112 ms 22908 KB
1_35.txt AC 167 ms 27004 KB
1_36.txt AC 75 ms 18812 KB
1_37.txt AC 256 ms 28028 KB
1_38.txt AC 293 ms 36220 KB
1_39.txt AC 240 ms 35196 KB
1_40.txt AC 166 ms 38652 KB
1_41.txt AC 529 ms 45436 KB
1_42.txt AC 60 ms 12668 KB
1_43.txt AC 69 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 20860 KB
1_47.txt AC 102 ms 23932 KB
1_48.txt AC 94 ms 23932 KB
1_49.txt AC 182 ms 34172 KB
1_50.txt AC 52 ms 13692 KB
1_51.txt AC 49 ms 11644 KB
1_52.txt AC 54 ms 14716 KB
1_53.txt AC 85 ms 18812 KB
1_54.txt AC 107 ms 31356 KB
1_55.txt AC 81 ms 23548 KB
1_56.txt AC 112 ms 29052 KB
1_57.txt AC 206 ms 33148 KB
1_58.txt AC 45 ms 10620 KB
1_59.txt AC 47 ms 11644 KB
1_60.txt AC 45 ms 11644 KB
1_61.txt AC 74 ms 14716 KB
1_62.txt AC 76 ms 21500 KB
1_63.txt AC 126 ms 30204 KB
1_64.txt AC 71 ms 19836 KB
1_65.txt AC 143 ms 30076 KB
1_66.txt AC 88 ms 23932 KB
1_67.txt AC 90 ms 23932 KB
1_68.txt AC 88 ms 23932 KB
1_69.txt AC 221 ms 32124 KB
1_70.txt AC 146 ms 39292 KB
1_71.txt AC 169 ms 39292 KB