Submission #55870820

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import Control.Monad
import qualified Data.ByteString.Char8 as BS
import Data.Char
import Data.List
import Data.Array
import qualified Data.Heap as H
import Data.Array.IO
main :: IO ()
main = do
  hwy@(h:_) <- bsGetLnInts
  ass <- replicateM h bsGetLnInts
  abc363e hwy ass
bsGetLnInts :: IO [Int]
bsGetLnInts = unfoldr (BS.readInt . BS.dropWhile isSpace) <$> BS.getLine
abc363e :: [Int] -> [[Int]] -> IO ()
abc363e [h,w,y] ass =
  do
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

import Control.Monad
import qualified Data.ByteString.Char8 as BS
import Data.Char
import Data.List

import Data.Array
import qualified Data.Heap as H
import Data.Array.IO

main :: IO ()
main = do
  hwy@(h:_) <- bsGetLnInts
  ass <- replicateM h bsGetLnInts
  abc363e hwy ass

bsGetLnInts :: IO [Int]
bsGetLnInts = unfoldr (BS.readInt . BS.dropWhile isSpace) <$> BS.getLine

abc363e :: [Int] -> [[Int]] -> IO ()
abc363e [h,w,y] ass =
  do
    seaside <- newArray bnds False
    forM_ seaside0ps (\p -> writeArray seaside p True)
    undersea <- newArray bnds False
    loop 1 seaside undersea (h * w) seasideQ0
  where
    bnds = ((1,1),(h,w))
    a = listArray bnds $ concat ass
    seaside0ps = [(i,1) | i <- [1..h]] ++ [(i,w) | w > 1, i <- [1..h]] ++
                 [(1,j) | j <- [2 .. pred w]] ++ [(h,j) | h > 1, j <- [2 .. pred w]]
    seasideQ0 = H.fromList [H.Entry ap p | p <- seaside0ps, let ap = a ! p, ap <= y ]

    loop :: Int -- 今から検討する時刻=水面高さ
         -> IOUArray (Int,Int) Bool -- 海に面した陸地フラグ
         -> IOUArray (Int,Int) Bool -- 水没済みフラグ
         -> Int -- 陸地マスの個数
         -> H.Heap (H.Entry Int (Int,Int)) -- 海に面した陸地の高さ順キュー
         -> IO ()
    loop t seaside underwater count q =
      case H.uncons q of
        Nothing       -> replicateM_ (y - pred t) (print count)
        Just (H.Entry aij ij@(i,j), q1)
          | t < aij   -> replicateM_ (aij -    t) (print count) >> loop aij seaside underwater count q
          | otherwise -> do
              writeArray underwater ij True
              q2 <- foldM (\ss ne -> do
                b1 <- readArray seaside    ne
                b2 <- readArray underwater ne
                let ane = a ! ne
                if b1 || b2 || ane > y then return ss else do
                  writeArray seaside ne True
                  return $ H.insert (H.Entry ane ne) ss
                ) q1 $ [(pred i, j) | i > 1] ++ [(succ i, j) | i < h] ++ [(i, pred j) | j > 1] ++ [(i, succ j) | j < w]
              loop t seaside underwater (pred count) q2

{-
IOUArray Bool で管理するようにして、間に合うようにはなったが、handで2つほどWAになってしまう。あれぇ？
タイムも割とぎりぎり。

キューをなるべく短く保つため、そもそもYより大きい場所はseasideに登録しないようにする。
groundはnotでチェックしているので、逆にする。

WAは多分あれだ。端を多重登録するのと同じで、WやHが1なんだ。くっそwww
-}

Submission Info

Compile Error

app/Main.hs:20:1: warning: [-Wincomplete-patterns]
    Pattern match(es) are non-exhaustive
    In an equation for ‘abc363e’:
        Patterns of type ‘[Int]’, ‘[[Int]]’ not matched:
            [] _
            [_] _
            [_, _] _
            (_:_:_:_:_) _
   |
20 | abc363e [h,w,y] ass =
   | ^^^^^^^^^^^^^^^^^^^^^...

app/Main.hs:31:65: warning: [-Wname-shadowing]
    This binding for ‘ap’ shadows the existing binding
      imported from ‘Control.Monad’ at app/Main.hs:1:1-20
      (and originally defined in ‘GHC.Base’)
   |
31 |     seasideQ0 = H.fromList [H.Entry ap p | p <- seaside0ps, let ap = a ! p, ap <= y ]
   |                                                                 ^^

Judge Result