codelegend's blog

By codelegend, 3 years ago, In English

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.

Full text and comments »

  • Vote: I like it
  • +46
  • Vote: I do not like it