結果

問題 No.68 よくある棒を切る問題 (2)
ユーザー tottoripapertottoripaper
提出日時 2014-11-17 19:16:54
言語 Haskell
(9.8.2)
結果
TLE  
(最新)
AC  
(最初)
実行時間 -
コード長 1,227 bytes
コンパイル時間 11,381 ms
コンパイル使用メモリ 196,564 KB
実行使用メモリ 185,620 KB
最終ジャッジ日時 2023-08-30 20:28:15
合計ジャッジ時間 45,167 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 4,002 ms
172,280 KB
testcase_01 AC 4,022 ms
167,048 KB
testcase_02 AC 4,012 ms
185,620 KB
testcase_03 TLE -
testcase_04 TLE -
testcase_05 TLE -
testcase_06 AC 3,693 ms
173,368 KB
testcase_07 AC 3,864 ms
178,292 KB
testcase_08 AC 4,824 ms
164,988 KB
testcase_09 AC 4,931 ms
178,552 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

ソースコード

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