Hi there!
I think, that the main problem with haskell programs is doing I/O within the time limit. For example "Help R2/D2" would be a really nice problem, but I testet my haskell O(n log(n) ) solution with the judge input data and noticed, that I need already 30 seconds for reading the data, whereas my algorithm solves the problem within 10 seconds (everything local measurements on my PC).
To hit the point: Does anyone know, how to do input better than in the code block below? For with better I/O routines I think, I could solve more problems in haskell, and I noticed, that there are some rather fast haskell solutions to other problems, which I think do their I/O in a better way.
By the way: Is it right, that Word32 gives worse performance than Int?
compute :: Int -> Int -> [(Int, Int)] -> (Int, Int)
compute k n list = (indres, countTo treeres indres (2^dep))
where
(indres, treeres) = foldl eval (0, construct k dep 1) list
dep = min (next2powerPot n) 17
eval (ind, tree) (val, times) = if a > 0 then error "impossible" else (max ind b, c)
where (a, b, c) = insert tree val times
readQ :: Int -> IO [(Int, Int)]
readQ 0 = return []
readQ k = do
l <- getLine
if head l == 'b' then do
let [t, v] = (map read . tail . words) l
r <- readQ (k - t)
return ((v, t):r)
else do
r <- readQ (k - 1)
return ((read l, 1):r)
readCase :: Int -> IO ()
readCase 0 = return ()
readCase cases = do
k <- readLn
n <- readLn
q <- readQ n
let (i, w) = compute k n q
putStrLn (show i ++ " " ++ show w)
readCase (cases - 1)
main :: IO ()
main = do
cases <- readLn
readCase cases
created
last reply
- 11
replies
- 1.5k
views
- 9
users
- 1
link