結果

問題 No.168 ものさし
ユーザー gigurururugigurururu
提出日時 2015-03-21 10:52:35
言語 Haskell
(9.8.2)
結果
CE  
(最新)
AC  
(最初)
実行時間 -
コード長 2,281 bytes
コンパイル時間 304 ms
コンパイル使用メモリ 174,592 KB
最終ジャッジ日時 2024-11-14 19:01:00
合計ジャッジ時間 653 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、clay言語の場合は開発者のデバッグのため、公開されます。

コンパイルメッセージ
Loaded package environment from /home/judge/.ghc/x86_64-linux-9.8.2/environments/default
[1 of 2] Compiling Main             ( Main.hs, Main.o )

Main.hs:29:33: error: [GHC-39999]
    • No instance for ‘MonadFail (ST s)’ arising from a use of ‘f’
    • In the first argument of ‘foldM’, namely ‘f’
      In the second argument of ‘(<$>)’, namely ‘foldM f [] queryList’
      In a stmt of a 'do' block:
        reverse . catMaybes <$> foldM f [] queryList
   |
29 |   reverse . catMaybes <$> foldM f [] queryList
   |                                 ^

Main.hs:53:9: error: [GHC-39999]
    • No instance for ‘MonadFail (ST s)’ arising from a use of ‘f’
    • In the first argument of ‘foldM’, namely ‘f’
      In a stmt of a 'do' block: foldM f False queryList
      In the second argument of ‘($)’, namely
        ‘do un <- newListArray bounds [lower .. upper] ::
                    ST s (STUArray s Int Int)
            let f True _ = return True
                f False x = ...
                find n = ...
                ....
            foldM f False queryList’
   |
53 |   foldM f False queryList
   |         ^

ソースコード

diff # 

import Control.Applicative
import Control.Monad
import Control.Monad.ST
import Data.Maybe
import Data.Either
import Data.List
import Data.Array.ST
import qualified Data.ByteString.Char8 as B

unionfind :: (Int,Int) -> [Either Int (Int,Int)] -> [Int]
unionfind bounds@(lower,upper) queryList = runST $ do
  un <- newListArray bounds [lower..upper] :: ST s (STUArray s Int Int)
  let 
      f ret x = do
        t <- either find union x
        return (t:ret)
      find n = do
        nn <- readArray un n
        if n==nn then return (Just n) else do
          Just nnn <- find nn
          writeArray un n nnn
          return (Just nnn)
      union (a,b) = do
        Just aa <- find a
        Just bb <- find b
        bbb <- readArray un bb
        writeArray un aa bbb
        return Nothing
  reverse . catMaybes <$> foldM f [] queryList

unionfindcheck :: (Int,Int) -> [Either Int (Int,Int)] -> Bool
unionfindcheck bounds@(lower,upper) queryList = runST $ do
  un <- newListArray bounds [lower..upper] :: ST s (STUArray s Int Int)
  let 
      f True  _ = return True
      f False x = do
        either find union x
        Just a <- find lower
        Just b <- find upper
        return (a==b)
      find n = do
        nn <- readArray un n
        if n==nn then return (Just n) else do
          Just nnn <- find nn
          writeArray un n nnn
          return (Just nnn)
      union (a,b) = do
        Just aa <- find a
        Just bb <- find b
        bbb <- readArray un bb
        writeArray un aa bbb
        return Nothing
  foldM f False queryList

hypot2 x y = x*x+y*y

solve n ls = bsearch 0 150000000
  where
    dst = [((i,j),hypot2 (xi-xj) (yi-yj))|(i,[xi,yi])<-zip [0..] ls,(j,[xj,yj])<-zip [0..] ls,i<j]
    bsearch l r
      | l>=r      = l*10
      | check     = bsearch l c
      | otherwise = bsearch (c+1) r
        where
          c       = (l+r)`div`2
          check   = unionfindcheck (0,n-1) $ map (Right . fst) $ filter ((100*c*c>=).snd) dst
--          check   = a==b
--          [a,b]   = unionfind (0,n-1) $ (map (Right . fst) $ filter ((100*c*c>=).snd) dst)++(map Left [0,n-1])

main = do
  n  <- fst . fromJust . B.readInt <$> B.getLine
  ls <- replicateM n $ map (fst . fromJust . B.readInt) . B.words <$> B.getLine
  print $ solve n ls
0