結果

問題 No.599 回文かい
ユーザー こまるこまる
提出日時 2020-11-20 17:15:41
言語 Haskell
(9.8.2)
結果
WA  
(最新)
AC  
(最初)
実行時間 -
コード長 4,918 bytes
コンパイル時間 6,865 ms
コンパイル使用メモリ 230,740 KB
実行使用メモリ 205,764 KB
最終ジャッジ日時 2023-09-30 18:33:25
合計ジャッジ時間 8,930 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge11
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 3 ms
6,668 KB
testcase_01 AC 3 ms
6,752 KB
testcase_02 AC 2 ms
6,668 KB
testcase_03 AC 2 ms
6,696 KB
testcase_04 AC 4 ms
10,532 KB
testcase_05 AC 4 ms
9,704 KB
testcase_06 AC 4 ms
10,128 KB
testcase_07 AC 5 ms
12,580 KB
testcase_08 AC 5 ms
10,524 KB
testcase_09 AC 4 ms
9,760 KB
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 AC 462 ms
192,652 KB
testcase_17 AC 532 ms
205,764 KB
testcase_18 AC 3 ms
7,000 KB
testcase_19 AC 3 ms
7,036 KB
testcase_20 AC 3 ms
7,056 KB
evil_0.txt WA -
権限があれば一括ダウンロードができます
コンパイルメッセージ
Loaded package environment from /home/judge/.ghc/x86_64-linux-9.6.1/environments/default
[1 of 2] Compiling Main             ( Main.hs, Main.o )
[2 of 2] Linking a.out

ソースコード

diff # 

{-# LANGUAGE BangPatterns       #-}
{-# LANGUAGE NumericUnderscores #-}

import           Control.Monad
import           Control.Monad.Cont
import           Control.Monad.ST
import           Control.Monad.State
import           Data.Bool
import qualified Data.ByteString.Char8             as BSC8
import           Data.Char
import           Data.Coerce
import           Data.Int
import           Data.Maybe
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           Unsafe.Coerce

modulus :: Int
modulus = 1_000_000_007
{-# INLINE modulus #-}

main :: IO ()
main = do
  lcp <- VUM.unsafeNew (10001 * 10001) :: IO (VUM.IOVector Int16)
  dp <- VUM.unsafeNew 10000 :: IO (VUM.IOVector Int)
  s <- VU.fromList <$> getLine
  rev (VU.length s) $ \i -> rev (VU.length s) $ \j -> do
    item <- VUM.unsafeRead lcp ((i + 1) * 10001 + j + 1)
    VUM.unsafeWrite lcp (i * 10001 + j) (bool 0 (item + 1) (s VU.! i == s VU.! j))
  VUM.unsafeWrite dp 0 1
  range 0 (VU.length s `div` 2 - 1) $ \i -> rev' i $ \k -> do
    item <- VUM.unsafeRead lcp (k * 10001 + (VU.length s - i - 1))
    when (unsafeCoerce item >= i - k + 1) $ do
      dpk <- VUM.unsafeRead dp k
      VUM.unsafeModify dp (flip mod modulus . (+ dpk)) (i + 1)
  d <- VU.unsafeFreeze dp
  print $ VU.foldl1' (\acc m -> (acc + m) `mod` modulus) $ VU.take (VU.length s) d

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

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

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

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

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

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

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

rev1' :: Monad m => Int -> (Int -> m ()) -> m ()
rev1' n = flip VFSM.mapM_ (streamRG n 1 const 0 (-) 1)
{-# INLINE rev1' #-}

range :: Monad m => Int -> Int -> (Int -> m ()) -> m ()
range l r = flip VFSM.mapM_ (streamG l r const 0 (+) 1)
{-# INLINE range #-}

rangeR :: Monad m => Int -> Int -> (Int -> m ()) -> m ()
rangeR r l = flip VFSM.mapM_ (streamRG r l const 0 (-) 1)
{-# INLINE rangeR #-}

forP :: Monad m => Int -> (Int -> m ()) -> m ()
forP p = flip VFSM.mapM_ (streamG 2 p (^) 2 (+) 1)
{-# INLINE forP #-}

forG :: Monad m => Int -> Int -> (Int -> Int -> Int) -> Int -> (Int -> Int -> Int) -> Int -> (Int -> m ()) -> m ()
forG l r f p g d = flip VFSM.mapM_ (streamG l r f p g d)
{-# INLINE forG #-}

forRG :: Monad m => Int -> Int -> (Int -> Int -> Int) -> Int -> (Int -> Int -> Int) -> Int -> (Int -> m ()) -> m ()
forRG r l f p g d = flip VFSM.mapM_ (streamRG r l f p g d)
{-# INLINE forRG #-}

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

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

withBreakIO :: ((r -> ContT r IO b) -> ContT r IO r) -> IO r
withBreakIO = flip runContT pure . callCC
{-# INLINE withBreakIO #-}

withBreakST :: ((r -> ContT r (ST s) b) -> ContT r (ST s) r) -> (ST s) r
withBreakST = flip runContT pure . callCC
{-# INLINE withBreakST #-}

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 #-}
seqInput :: Int -> IO (VU.Vector Int)
seqInput n = VU.unfoldrN n (runCParser int) <$> BSC8.getLine
{-# INLINE seqInput #-}
readInt :: BSC8.ByteString -> Int
readInt = fst . fromJust . BSC8.readInt
{-# INLINE readInt #-}
getInt :: IO Int
getInt = readInt <$> BSC8.getLine
{-# INLINE getInt #-}
readIntList :: BSC8.ByteString -> [Int]
readIntList = map readInt . BSC8.words
{-# INLINE readIntList #-}
getIntList :: IO [Int]
getIntList = readIntList <$> BSC8.getLine
{-# INLINE getIntList #-}
0