Submission #3415217


Source Code Expand

import Control.Monad
import Data.Maybe
import Debug.Trace
import Data.List
import qualified Data.Map.Strict as Map
import qualified Data.IntMap.Strict as IntMap
import qualified Data.Set as Set
import qualified Data.IntSet as IntSet

main :: IO ()
main = do
  k <- readLn :: IO Int
  rs <- replicateM (2^k) readLn :: IO [Int]
  let dic = Map.fromListWith (+) . join $ solve k rs
  forM_ rs (\r -> print $ dic Map.! r)

type Prob = (Int, Double)

prob :: Prob -> Prob -> [Prob]
prob (p, pp) (q, qp)
  = let e = 1 / (1 + 10**(fromIntegral (q - p) / 400))
    in [(p, pp * qp * e), (q, pp * qp * (1 - e))]

solve k rs = foldr (.) id (replicate k proceed) $ initial
  where
    initial = map (:[]) . zip rs $ repeat 1 :: [[Prob]]

proceed :: [[Prob]] -> [[Prob]]
proceed [] = []
proceed (ps:qs:probs) = join [prob p q | p <- ps, q <- qs] : proceed probs

Submission Info

Submission Time
Task C - トーナメント
User utopian
Language Haskell (GHC 7.10.3)
Score 0
Code Size 880 Byte
Status TLE
Exec Time 2142 ms
Memory 645116 KB

Judge Result

Set Name All
Score / Max Score 0 / 4
Status
AC × 2
TLE × 4
Set Name Test Cases
All 00, 01, 02, 03, 90, 91
Case Name Status Exec Time Memory
00 TLE 2137 ms 559612 KB
01 TLE 2130 ms 436604 KB
02 TLE 2142 ms 645116 KB
03 TLE 2129 ms 423292 KB
90 AC 1 ms 508 KB
91 AC 1 ms 764 KB