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 ghc -O2
)
Edit: Resolved, had to disable stdout
buffering, with hSetBuffering stdout NoBuffering
.