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 |
|
|
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 |