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