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
.
What flushes the output here?
IIUC the interact function is fully lazy, it forces and prints one character at a time. And this force usually forces the computation to happen.
So here, tracing back, it forces
unlines
which forcesmap show
which forcessolve
. And solve consumes input, but only from the second query onwards. And I think all the functions I used are fully lazy.(I might be wrong about my assumptions of which functions are lazy though.)
Ah okay, turns out I also need to disable buffering for
stdout
, byhSetBuffering stdout NoBuffering
. It works now! submission — 117843764.I guess without this, the flushing is environment dependent? Not sure.