結果
問題 | No.210 探し物はどこですか? |
ユーザー | autotaker1984 |
提出日時 | 2015-04-08 12:47:56 |
言語 | Haskell (9.8.2) |
結果 |
AC
|
実行時間 | 784 ms / 2,000 ms |
コード長 | 2,911 bytes |
コンパイル時間 | 3,080 ms |
コンパイル使用メモリ | 183,716 KB |
実行使用メモリ | 12,676 KB |
最終ジャッジ日時 | 2023-09-17 16:10:56 |
合計ジャッジ時間 | 17,170 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 42 ms
11,988 KB |
testcase_01 | AC | 192 ms
12,080 KB |
testcase_02 | AC | 393 ms
12,284 KB |
testcase_03 | AC | 12 ms
11,996 KB |
testcase_04 | AC | 8 ms
11,988 KB |
testcase_05 | AC | 7 ms
11,972 KB |
testcase_06 | AC | 13 ms
11,936 KB |
testcase_07 | AC | 7 ms
11,980 KB |
testcase_08 | AC | 12 ms
11,956 KB |
testcase_09 | AC | 12 ms
11,968 KB |
testcase_10 | AC | 13 ms
11,928 KB |
testcase_11 | AC | 12 ms
12,076 KB |
testcase_12 | AC | 12 ms
12,020 KB |
testcase_13 | AC | 52 ms
12,128 KB |
testcase_14 | AC | 62 ms
11,992 KB |
testcase_15 | AC | 62 ms
12,076 KB |
testcase_16 | AC | 52 ms
12,120 KB |
testcase_17 | AC | 62 ms
11,960 KB |
testcase_18 | AC | 63 ms
12,116 KB |
testcase_19 | AC | 62 ms
12,068 KB |
testcase_20 | AC | 62 ms
12,080 KB |
testcase_21 | AC | 62 ms
12,060 KB |
testcase_22 | AC | 62 ms
11,980 KB |
testcase_23 | AC | 352 ms
12,132 KB |
testcase_24 | AC | 342 ms
12,060 KB |
testcase_25 | AC | 353 ms
12,148 KB |
testcase_26 | AC | 353 ms
12,032 KB |
testcase_27 | AC | 352 ms
12,032 KB |
testcase_28 | AC | 352 ms
12,124 KB |
testcase_29 | AC | 352 ms
12,076 KB |
testcase_30 | AC | 352 ms
12,128 KB |
testcase_31 | AC | 342 ms
12,284 KB |
testcase_32 | AC | 352 ms
12,148 KB |
testcase_33 | AC | 743 ms
12,400 KB |
testcase_34 | AC | 752 ms
12,464 KB |
testcase_35 | AC | 732 ms
12,384 KB |
testcase_36 | AC | 784 ms
12,676 KB |
testcase_37 | AC | 741 ms
12,500 KB |
testcase_38 | AC | 642 ms
12,204 KB |
testcase_39 | AC | 643 ms
12,144 KB |
testcase_40 | AC | 642 ms
12,216 KB |
testcase_41 | AC | 652 ms
12,204 KB |
testcase_42 | AC | 643 ms
12,224 KB |
testcase_43 | AC | 3 ms
8,284 KB |
testcase_44 | AC | 7 ms
11,936 KB |
testcase_45 | AC | 12 ms
11,996 KB |
コンパイルメッセージ
Loaded package environment from /home/judge/.ghc/x86_64-linux-9.6.1/environments/default [1 of 2] Compiling Main ( Main.hs, Main.o ) [2 of 2] Linking a.out
ソースコード
{-# LANGUAGE MultiParamTypeClasses,FlexibleContexts,FlexibleInstances,TypeSynonymInstances,BangPatterns,RankNTypes,TupleSections #-} import Control.Monad import Control.Monad.ST import Control.Applicative import Control.Arrow import Debug.Trace import Text.Printf import Data.List hiding(insert) import Data.Int import Data.Bits import Data.Maybe import Data.Monoid import Data.Array.Unboxed import Data.Array.ST import qualified Data.Map as M import qualified Data.Set as S import qualified Data.ByteString.Char8 as B readInt = fromJust . fmap fst . B.readInt readInts = map readInt . B.words <$> B.getLine readIntPair = l2p . map readInt . take 2 . B.words <$> B.getLine readLns :: Read a => IO [a] readLns = map read . words <$> getLine cmpFst (a,_) (b,_) = compare a b cmpSnd (_,a) (_,b) = compare a b cmpLen a b = length a `compare` length b swap (a,b) = (b,a) l2p (a:b:_) = (a,b) p2l (a,b) = [a,b] itof :: Int -> Double itof = fromIntegral defaultArray :: (IArray a e,Ix i) => e -> (i,i) -> [(i,e)] -> a i e defaultArray = accumArray $ curry snd flatten :: [(a,[(b,c)])] -> [((a,b),c)] flatten = (=<<) $ uncurry $ fmap . first . (,) stepM_ :: Monad m => a -> (a -> Bool) -> (a -> a) -> (a -> m ()) -> m () stepM_ i judge incr step = sub i where sub i | judge i = step i >> sub (incr i) | otherwise = return () thru :: Monad m => (v -> m ()) -> v -> m v thru m v = m v >> return v inf = maxBound `div` 2 :: Int main = do n <- readLn :: IO Int ps <- map ((/1000).itof)<$> readInts qs <- map ((/100).itof) <$> readInts let go !e c queue | c > 3000 * n = e | otherwise = let (p,q) = minElem queue in let queue' = insert (p * (1 - q)) q $ deleteMin queue in go (e - p * itof c) (c+1) queue' let p0 = map negate $ zipWith (*) ps qs let q0 = foldr (uncurry insert) emptyHP $ zip p0 qs printf "%.5f\n" $ go 0 1 q0 data Heap k v = Null | Fork !k !v !(Heap k v) !(Heap k v) {-# INLINE emptyHP #-} emptyHP :: Heap k v emptyHP = Null {-# INLINE isEmpty #-} isEmpty :: Heap k v -> Bool isEmpty Null = True isEmpty _ = False {-# INLINE minElem #-} minElem :: Heap k v -> (k,v) minElem (Fork k v _ _) = (k,v) minElem Null = error "min for empty queue is not supported" {-# INLINE minKey #-} minKey :: Heap k v -> k minKey (Fork k _ _ _) = k minKey Null = error "min for empty queue is not supported" {-# INLINE deleteMin #-} deleteMin :: (Ord k) => Heap k v -> Heap k v deleteMin (Fork _ _ a b) = merge a b deleteMin _ = undefined {-# INLINE merge #-} insert :: (Ord k) => k -> v -> Heap k v -> Heap k v insert k v a = merge (Fork k v Null Null) a merge :: (Ord k) => Heap k v -> Heap k v -> Heap k v merge a Null = a merge Null b = b merge a b | minKey a <= minKey b = jo a b | otherwise = jo b a where jo (Fork k v _a _b) _c = Fork k v _b (merge _a _c) jo _ _ = undefined