結果

問題 No.68 よくある棒を切る問題 (2)
コンテスト
ユーザー tottoripaper
提出日時 2014-11-17 19:16:54
言語 Haskell
(9.10.1)
結果
TLE  
(最新)
AC  
(最初)
実行時間 -
コード長 1,227 bytes
コンパイル時間 9,850 ms
コンパイル使用メモリ 235,112 KB
実行使用メモリ 362,396 KB
最終ジャッジ日時 2025-01-02 16:48:07
合計ジャッジ時間 72,772 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 1 TLE * 9
権限があれば一括ダウンロードができます
コンパイルメッセージ
Loaded package environment from /home/judge/.ghc/x86_64-linux-9.10.1/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