I am attempting to solve 1520F1 - Guess the K-th Zero (Easy version) in Haskell.
import Control.Arrow ((>>>)) main = interact $ lines >>> (\(nt:ls) -> head (words nt) : ls) >>> map read >>> solve >>> map show >>> unlines data Query = Ask Int Int | Answer Int instance Show Query where show (Ask l r) = "? " ++ show l ++ " " ++ show r show (Answer x) = "! " ++ show x solve :: [Int] -> [Query] solve (n:k:rs) = go 1 n rs where go lo hi xs | lo == hi = [Answer lo] | otherwise = let mid = (lo + hi) `div` 2 in Ask 1 mid : (let (lo', hi') = (if head xs + k > mid then (mid + 1, hi) else (lo, mid)) in go lo' hi' (tail xs))
I believe I have ensured maximum laziness while checking the query responses — I only force
xs in the tail of the returned query list.
The code runs fine locally. But I keep getting Idleness limit exceeded on the sample case: 117826356
Am I missing some important detail here? Or perhaps it has something to do with the exact compilation options CF uses? (I am just using
Edit: Resolved, had to disable
stdout buffering, with
hSetBuffering stdout NoBuffering.