結果

問題 No.68 よくある棒を切る問題 (2)
ユーザー tottoripapertottoripaper
提出日時 2014-11-17 19:16:54
言語 Haskell
(9.8.2)
結果
TLE  
(最新)
AC  
(最初)
実行時間 -
コード長 1,227 bytes
コンパイル時間 7,634 ms
コンパイル使用メモリ 206,464 KB
実行使用メモリ 182,400 KB
最終ジャッジ日時 2024-06-10 19:57:46
合計ジャッジ時間 36,711 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 3,624 ms
169,216 KB
testcase_01 AC 3,643 ms
164,992 KB
testcase_02 AC 3,669 ms
176,256 KB
testcase_03 AC 4,952 ms
176,256 KB
testcase_04 AC 4,865 ms
178,432 KB
testcase_05 TLE -
testcase_06 AC 3,387 ms
170,240 KB
testcase_07 AC 3,534 ms
175,360 KB
testcase_08 AC 4,415 ms
159,744 KB
testcase_09 AC 4,548 ms
174,208 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
Loaded package environment from /home/judge/.ghc/x86_64-linux-9.8.2/environments/default
[1 of 2] Compiling Main             ( Main.hs, Main.o )
[2 of 2] Linking a.out

ソースコード

diff # 

import Control.Applicative
import qualified Data.Vector as V
import qualified Data.ByteString.Char8 as B
import Data.Maybe (mapMaybe)
import Text.Printf

data Heap a = Empty | Heap {value :: a, left :: Heap a, right :: Heap a}

singleton :: a -> Heap a
singleton x = Heap x Empty Empty

meld :: (Ord a) => Heap a -> Heap a -> Heap a
meld Empty h2 = h2
meld h1 Empty = h1
meld h1 h2
  | value h1 >= value h2 = h1 {left = meld (right h1) h2, right = left h1}
  | otherwise = h2 {left = meld (right h2) h1, right = left h2}

removeMin :: (Ord a) => Heap a -> (a, Heap a)
removeMin h = (value h, meld (left h) (right h))

readNum :: (Num a) => IO [a]
readNum = map (fromIntegral . fst) . mapMaybe B.readInt . B.words <$> B.getLine

main = do
  n <- readLn
  ls <- readNum :: IO [Double]
  _ <- getLine
  ks <- readNum
  let
    ls' = V.fromList ls
    heap = foldr (\i h -> meld (singleton (ls' V.! i, i, 1)) h) Empty $ [0..n-1]
    f t h
      | t > 500000 = []
      | otherwise = let ((x, y, z), h') = removeMin h
                    in x : f (t+1) (meld (singleton (ls' V.! y / (z+1), y, z+1)) h')
    xs = V.fromList $ f 1 heap
    in mapM (printf "%.30f\n" . (xs V.!) . (subtract 1)) ks
0