Submission #48028582

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 qualified Data.IntMap as IM
main :: IO ()
main = do
  [n,k] <- bsGetLnInts
  xys <- replicateM n bsGetLnInts
  let ans = abc330f n k xys
  print ans
bsGetLnInts :: IO [Int]
bsGetLnInts = unfoldr (BS.readInt . BS.dropWhile isSpace) <$> BS.getLine
abc330f :: Int -> Int -> [[Int]] -> Int
abc330f n k xys = sat
  where
    xm = mkfunc $ IM.fromListWith (+) [(x, 1) | x:_   <- xys]  -- X軸について数える
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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

import qualified Data.IntMap as IM

main :: IO ()
main = do
  [n,k] <- bsGetLnInts
  xys <- replicateM n bsGetLnInts
  let ans = abc330f n k xys
  print ans

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

abc330f :: Int -> Int -> [[Int]] -> Int
abc330f n k xys = sat
  where
    xm = mkfunc $ IM.fromListWith (+) [(x, 1) | x:_   <- xys]  -- X軸について数える
    ym = mkfunc $ IM.fromListWith (+) [(y, 1) | _:y:_ <- xys]  -- Y軸
    (_unsat, sat) = binarySearch (\r -> evalFunc xm r + evalFunc ym r <= k) (-1) 1_000_000_001 


-- mkfuncのIntMapを関数として計算する
evalFunc :: IM.IntMap Int -> Int -> Int
evalFunc im x =
  case (IM.lookupLE x im, IM.lookupGT x im) of
    (Nothing, _) -> tooBig
    (_, Nothing) -> 0
    (Just (xl,yl), Just (xu,yu)) -> yl + div ((yu - yl) * (x - xl)) (xu - xl)

tooBig :: Int
tooBig = div maxBound 2

-- 作る幅とコストの関係を表すIntMapを作る
mkfunc :: IM.IntMap Int -> IM.IntMap Int
mkfunc im = IM.fromList $ loop width 0 wsL accsL wsR accsR
  where
    width = fst (IM.findMax im) - fst (IM.findMin im) -- 幅
    (rsL, cntsL) = unzip $ IM.toAscList im             -- X軸の値リストとカウントリスト relative position
    wsL = zipWith (-) (tail rsL) rsL               -- それぞれ順に押し込む距離 width に変換
    accsL = scanl1 (+) cntsL                          -- 押し込む累積の粒の数
    (rsR, cntsR) = unzip $ IM.toDescList im -- 今度は右からの
    wsR = zipWith (-) rsR (tail rsR)  -- 右端からの押し込み距離
    accsR = scanl1 (+) cntsR -- 押し込む累積の粒の数
    loop wid cost wsL accsL wsR accsR = (wid, cost) : 
      case () of
        () | wid == 0   -> []
           | a1L <= a1R -> loop (wid - w1L) (cost + w1L * a1L) (tail wsL) (tail accsL) wsR accsR
           | otherwise  -> loop (wid - w1R) (cost + w1R * a1R) wsL accsL (tail wsR) (tail accsR)
      where
        a1L = head accsL
        a1R = head accsR
        w1L = head wsL
        w1R = head wsR

-- @gotoki_no_joe
binarySearch :: (Int -> Bool) -> Int -> Int -> (Int, Int)
binarySearch prop unsat sat = loop unsat sat
  where
    loop a b
      | ende   = (a, b)
      | prop m = loop a m
      | True   = loop m b
      where
        ende = a == m || b == m 
        m = div (a + b) 2

{-
WAx7した。satに+1するのを忘れたのが原因か？
-}

Submission Info

Compile Error

app/Main.hs:19:9: warning: [-Wunused-matches]
    Defined but not used: ‘n’
   |
19 | abc330f n k xys = sat
   |         ^

app/Main.hs:48:19: warning: [-Wname-shadowing]
    This binding for ‘wsL’ shadows the existing binding
      bound at app/Main.hs:43:5
   |
48 |     loop wid cost wsL accsL wsR accsR = (wid, cost) : 
   |                   ^^^

app/Main.hs:48:23: warning: [-Wname-shadowing]
    This binding for ‘accsL’ shadows the existing binding
      bound at app/Main.hs:44:5
   |
48 |     loop wid cost wsL accsL wsR accsR = (wid, cost) : 
   |                       ^^^^^

app/Main.hs:48:29: warning: [-Wname-shadowing]
    This binding for ‘wsR’ shadows the existing binding
      bound at app/Main.hs:46:5
   |
48 |     loop wid cost wsL accsL wsR accsR = (wid, cost) : 
   |                             ^^^

app/Main.hs:48:33: warning: [-Wname-shadowing]
    This binding for ‘accsR’ shadows the existing binding
      bound at app/Main.hs:47:5
   |
48 |     loop wid cost wsL accsL wsR accsR = (wid, cost) : 
   |                                 ^^^^^

Judge Result