結果

問題 No.1238 選抜クラス
ユーザー こまるこまる
提出日時 2020-10-22 11:07:22
言語 Haskell
(9.8.2)
結果
CE  
(最新)
AC  
(最初)
実行時間 -
コード長 7,114 bytes
コンパイル時間 191 ms
コンパイル使用メモリ 156,032 KB
最終ジャッジ日時 2024-11-14 23:52:30
合計ジャッジ時間 630 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、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:18:1: error: [GHC-87110]
    Could not load module ‘GHC.Integer.GMP.Internals’.
    It is a member of the hidden package ‘integer-gmp-1.1’.
    Use -v to see a list of the files searched for.
   |
18 | import qualified GHC.Integer.GMP.Internals         as GMP
   | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

ソースコード

diff # 

{-# LANGUAGE BangPatterns #-}
{-# LANGUAGE MagicHash    #-}

import           Control.Monad
import           Control.Monad.State
import           Data.Bits
import           Data.Bool
import           Data.Char
import           Data.IORef
import           Data.Word
import           GHC.Exts
import           Unsafe.Coerce
import qualified Data.ByteString                   as BS
import qualified Data.ByteString.Char8             as BSC8
import qualified Data.Vector.Fusion.Stream.Monadic as VFSM
import qualified Data.Vector.Unboxed               as VU
import qualified Data.Vector.Unboxed.Mutable       as VUM
import qualified GHC.Integer.GMP.Internals         as GMP

modulo :: Int
modulo = 1000000007
{-# INLINE modulo #-}

main :: IO ()
main = do
  [n, k] <- map (read :: String -> Int) . words <$> getLine
  an <- seqInput n
  let bn = VU.map (\i -> i - k) an
  dp <- VUM.unsafeNew 20100
  VUM.unsafeWrite dp 10000 (1 :: Int)
  rep n $ \i -> do
    if bn VU.! i < 0
      then do
        repStep' (- bn VU.! i) 20000 1 $ \j -> do
          item <- VUM.unsafeRead dp j
          VUM.unsafeModify dp (flip mod modulo . (+ item)) (j + bn VU.! i)
      else if bn VU.! i > 0
        then do
          rev' (20000 - bn VU.! i) $ \j -> do
            item <- VUM.unsafeRead dp j
            VUM.unsafeModify dp (flip mod modulo . (+ item)) (j + bn VU.! i)
        else rep' 20000 $ \j -> VUM.unsafeModify dp (flip mod modulo . (* 2)) j
  ans <- newIORef (modulo - 1)
  repStep' 10000 20000 1 $ \i -> do
    item <- VUM.unsafeRead dp i
    modifyIORef' ans (flip mod modulo . (+ item))
  print =<< readIORef ans

-------------------------------------------------------------------------------
-- Input
-------------------------------------------------------------------------------

type CParser a = StateT BSC8.ByteString Maybe a
runCParser :: CParser a -> BSC8.ByteString -> Maybe (a, BSC8.ByteString)
runCParser = runStateT
{-# INLINE runCParser #-}
int :: CParser Int
int = coerce $ BSC8.readInt . BSC8.dropWhile isSpace
{-# INLINE int #-}
int1 :: CParser Int
int1 = fmap (subtract 1) int
{-# INLINE int1 #-}
char :: CParser Char
char = coerce BSC8.uncons
{-# INLINE char #-}
byte :: CParser Word8
byte = coerce BS.uncons
{-# INLINE byte #-}
skipSpaces :: CParser ()
skipSpaces = modify' (BSC8.dropWhile isSpace)
{-# INLINE skipSpaces #-}
seqInput :: Int -> IO (VU.Vector Int)
seqInput n = VU.unfoldrN n (runCParser int) <$> BSC8.getLine
{-# INLINE seqInput #-}
parseN2 :: Int -> IO (VU.Vector (Int, Int))
parseN2 n = VU.unfoldrN n (runCParser $ (,) <$> int <*> int) <$> BSC8.getContents
{-# INLINE parseN2 #-}
parseN3 :: Int -> IO (VU.Vector (Int, Int, Int))
parseN3 n = VU.unfoldrN n (runCParser $ (,,) <$> int <*> int <*> int) <$> BSC8.getContents
{-# INLINE parseN3 #-}
parseN4 :: Int -> IO (VU.Vector (Int, Int, Int, Int))
parseN4 n = VU.unfoldrN n (runCParser $ (,,,) <$> int <*> int <*> int <*> int) <$> BSC8.getContents
{-# INLINE parseN4 #-}
parseN5 :: Int -> IO (VU.Vector (Int, Int, Int, Int, Int))
parseN5 n = VU.unfoldrN n (runCParser $ (,,,,) <$> int <*> int <*> int <*> int <*> int) <$> BSC8.getContents
{-# INLINE parseN5 #-}
parseANBN :: Int -> IO (VU.Vector Int, VU.Vector Int)
parseANBN n = VU.unzip . VU.unfoldrN n (runCParser $ (,) <$> int <*> int) <$> BSC8.getContents
{-# INLINE parseANBN #-}
parseANBNCN :: Int -> IO (VU.Vector Int, VU.Vector Int, VU.Vector Int)
parseANBNCN n = VU.unzip3 . VU.unfoldrN n (runCParser $ (,,) <$> int <*> int <*> int) <$> BSC8.getContents
{-# INLINE parseANBNCN #-}
type Query5 = (Int, Int, Int, Int, Int)
query5Parser :: CParser Query5
query5Parser = do
  skipSpaces
  t <- char
  case t of
    '0' -> (,,,,) 0 <$> int <*> int <*> int    <*> int
    _   -> (,,,,) 1 <$> int <*> int <*> pure 0 <*> pure 0
parseQ5 :: Int -> IO (VU.Vector Query5)
parseQ5 n = VU.unfoldrN n (runCParser query5Parser) <$> BSC8.getContents
{-# INLINE parseQ5 #-}

-------------------------------------------------------------------------------
-- Utils
-------------------------------------------------------------------------------
-- * integer
fi :: Int -> Integer
fi = fromIntegral
{-# INLINE fi #-}

fI :: Integer -> Int
fI = fromInteger
{-# INLINE fI #-}

ceilPow2 :: Int -> Int
ceilPow2 n
  | n > 1     = (-1) .>>>. (clz (n - 1)) + 1
  | otherwise = 1

floorPow2 :: Int -> Int
floorPow2 n
  | n >= 1    = 1 .<<. (63 - (clz n))
  | otherwise = 0

powModInt :: Int -> Int -> Int -> Int
powModInt a n mo = fI $ GMP.powModInteger (fi a) (fi n) (fi mo)

recipModInt :: Int -> Int -> Int
recipModInt a mo = fI $ GMP.recipModInteger (fi a) (fi mo)

floorSqrt :: Int -> Int
floorSqrt = floor . sqrt . fromIntegral

floorLog2 :: Int -> Int
floorLog2 x = fromIntegral $ y .>>. 52 - 1023
  where
    y :: Word64
    y = unsafeCoerce (fromIntegral x :: Double)
-- //integer

-- * bits
infixl 8 .<<., .>>.
infixl 6 .^.

(.<<.) :: Bits b => b -> Int -> b
(.<<.) = unsafeShiftL
{-# INLINE (.<<.) #-}

(.>>.) :: Bits b => b -> Int -> b
(.>>.) = unsafeShiftR
{-# INLINE (.>>.) #-}

(.^.) :: Bits b => b -> b -> b
(.^.)  = xor
{-# INLINE (.^.)  #-}

clz :: FiniteBits fb => fb -> Int
clz = countLeadingZeros
{-# INLINE clz #-}

ctz :: FiniteBits fb => fb -> Int
ctz = countTrailingZeros
{-# INLINE ctz #-}

infixl 8 .>>>.
(.>>>.) :: Int -> Int -> Int
(.>>>.) (I# x#) (I# i#) = I# (uncheckedIShiftRL# x# i#)
{-# INLINE (.>>>.) #-}
-- //bits

-- * for
stream :: Monad m => Int -> Int -> VFSM.Stream m Int
stream !l !r = VFSM.Stream step l
  where
    step x
      | x < r     = return $ VFSM.Yield x (x + 1)
      | otherwise = return $ VFSM.Done
    {-# INLINE [0] step #-}
{-# INLINE [1] stream #-}

rep :: Monad m => Int -> (Int -> m ()) -> m ()
rep n = flip VFSM.mapM_ (stream 0 n)
{-# INLINE rep #-}

rep' :: Monad m => Int -> (Int -> m ()) -> m ()
rep' n = flip VFSM.mapM_ (stream 0 (n + 1))
{-# INLINE rep' #-}

rep1 :: Monad m => Int -> (Int -> m ()) -> m ()
rep1 n = flip VFSM.mapM_ (stream 1 (n + 1))
{-# INLINE rep1 #-}

streamR :: Monad m => Int -> Int -> VFSM.Stream m Int
streamR !l !r = VFSM.Stream step (r - 1)
  where
    step x
      | x >= l    = return $ VFSM.Yield x (x - 1)
      | otherwise = return $ VFSM.Done
    {-# INLINE [0] step #-}
{-# INLINE [1] streamR #-}

rev :: Monad m => Int -> (Int -> m ()) -> m ()
rev n = flip VFSM.mapM_ (streamR 0 n)
{-# INLINE rev #-}

rev' :: Monad m => Int -> (Int -> m ()) -> m ()
rev' n = flip VFSM.mapM_ (streamR 0 (n + 1))
{-# INLINE rev' #-}

rev1 :: Monad m => Int -> (Int -> m ()) -> m ()
rev1 n = flip VFSM.mapM_ (streamR 1 (n + 1))
{-# INLINE rev1 #-}

streamStep :: Monad m => Int -> Int -> Int -> VFSM.Stream m Int
streamStep !l !r !d = VFSM.Stream step l
  where
    step x
      | x < r     = return $ VFSM.Yield x (x + d)
      | otherwise = return $ VFSM.Done
    {-# INLINE [0] step #-}
{-# INLINE [1] streamStep #-}

repStep :: Monad m => Int -> Int -> Int -> (Int -> m ()) -> m ()
repStep l r d = flip VFSM.mapM_ (streamStep l r d)
{-# INLINE repStep #-}

repStep' :: Monad m => Int -> Int -> Int -> (Int -> m ()) -> m ()
repStep' l r d = flip VFSM.mapM_ (streamStep l (r + 1) d)
{-# INLINE repStep' #-}
-- //for
0