結果

問題 No.1219 Mancala Combo
ユーザー かりあげクン
提出日時 2020-09-25 13:23:44
言語 Haskell
(9.10.1)
結果
CE  
(最新)
AC  
(最初)
実行時間 -
コード長 12,718 bytes
コンパイル時間 299 ms
コンパイル使用メモリ 168,704 KB
最終ジャッジ日時 2024-11-14 23:50:26
合計ジャッジ時間 1,330 ms
ジャッジサーバーID
(参考情報)
judge2 / 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:52: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.
   |
52 | import qualified GHC.Integer.GMP.Internals         as GMP
   | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

Main.hs:53:1: error: [GHC-87110]
    Could not find module ‘GHC.Integer.Logarithms.Internals’.
    Use -v to see a list of the files searched for.
   |
53 | import qualified GHC.Integer.Logarithms.Internals  as Log
   | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

ソースコード

diff #
プレゼンテーションモードにする

{-# LANGUAGE BangPatterns #-}
{-# LANGUAGE CPP #-}
{-# LANGUAGE DerivingStrategies #-}
{-# LANGUAGE FlexibleContexts #-}
{-# LANGUAGE GeneralizedNewtypeDeriving #-}
{-# LANGUAGE MagicHash #-}
{-# LANGUAGE MultiParamTypeClasses #-}
{-# LANGUAGE RankNTypes #-}
{-# LANGUAGE RecordWildCards #-}
{-# LANGUAGE ScopedTypeVariables #-}
{-# LANGUAGE TypeApplications #-}
{-# LANGUAGE TypeFamilies #-}
{-# LANGUAGE UnboxedTuples #-}
{- base -}
import Control.Arrow
import Control.Monad
import Control.Monad.ST
import Data.Bits
import Data.Bool
import Data.Char
import Data.Coerce
import Data.Function
import Data.Functor.Identity
import Data.IORef
import Data.Ix
import Data.Monoid
import Data.Ord
import Data.Ratio
import Data.Semigroup
import Data.STRef
import Data.Void
import Data.Word
import GHC.Exts
import Unsafe.Coerce
{- array -}
import qualified Data.Array as Arr
import qualified Data.Array.IO as ArrIO
import qualified Data.Array.MArray as ArrMA
import qualified Data.Array.ST as ArrST
import qualified Data.Array.Unboxed as ArrU
{- bytestring -}
import qualified Data.ByteString as BS
import qualified Data.ByteString.Builder as BSB
import qualified Data.ByteString.Builder.Extra as BSBE
import qualified Data.ByteString.Builder.Prim as BSBP
import qualified Data.ByteString.Char8 as BSC8
import qualified Data.ByteString.Lazy as BSL
import qualified Data.ByteString.Lazy.Char8 as BSLC8
import qualified Data.ByteString.Short as BSS
import qualified Data.ByteString.Unsafe as BSU
{- integer-gmp -}
import qualified GHC.Integer.GMP.Internals as GMP
import qualified GHC.Integer.Logarithms.Internals as Log
{- vector -}
import qualified Data.Vector as V
import qualified Data.Vector.Fusion.Stream.Monadic as VFSM
import qualified Data.Vector.Generic as VG
import qualified Data.Vector.Generic.Mutable as VGM
import qualified Data.Vector.Mutable as VM
import qualified Data.Vector.Primitive as VP
import qualified Data.Vector.Primitive.Mutable as VPM
import qualified Data.Vector.Storable as VS
import qualified Data.Vector.Storable.Mutable as VSM
import qualified Data.Vector.Unboxed as VU
import qualified Data.Vector.Unboxed.Mutable as VUM
-------------------------------------------------------------------------------
#define MOD 1000000007
#define Fact_CACHE_SIZE 100100
#define LOG_FACT_CACHE_SIZE 1024
-------------------------------------------------------------------------------
fi :: Int -> Integer
fi = fromIntegral
{-# INLINE fi #-}
fI :: Integer -> Int
fI = fromInteger
{-# INLINE fI #-}
floorSqrt :: Int -> Int
floorSqrt = floor . sqrt . fromIntegral
{-# INLINE floorSqrt #-}
floorLog2 :: Int -> Int
floorLog2 x = fromIntegral $ unsafeShiftR y 52 - 1023
where
y :: Word64
y = unsafeCoerce (fromIntegral x :: Double)
{-# INLINE floorLog2 #-}
powModInt :: Int -> Int -> Int -> Int
powModInt a b c = fI $ GMP.powModInteger (fi a) (fi b) (fi c)
{-# INLINE powModInt #-}
recipModInt :: Int -> Int -> Int
recipModInt a m = fI $ GMP.recipModInteger (fi a) (fi m)
{-# INLINE recipModInt #-}
gcdext :: Int -> Int -> (Int, Int, Int) -- a * x + b * y = d => (x, y, d) (d = gcd a b)
gcdext a b = (x, y, d)
where
d = gcd a b
(x, y) = case GMP.gcdExtInteger (fi a) (fi b) of
(# p, q #) -> (fI p, fI q)
{-# INLINE gcdext #-}
modInv :: Int -> Int -> Int
modInv a mo
| 1 == g = mkPos i
| otherwise = -1
where
(i, _, g) = gcdext a mo
mkPos x
| x < 0 = x + mo
| otherwise = x
{-# INLINE modInv #-}
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 #-}
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 #-}
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 #-}
infixl 8 `shiftRL`, `unsafeShiftRL`
shiftRL :: Int -> Int -> Int
shiftRL = unsafeShiftRL
{-# INLINE shiftRL #-}
unsafeShiftRL :: Int -> Int -> Int
unsafeShiftRL (I# x#) (I# i#) = I# (uncheckedIShiftRL# x# i#)
{-# INLINE unsafeShiftRL #-}
lowerBoundM :: (Monad m) => Int -> Int -> (Int -> m Bool) -> m Int
lowerBoundM low high p = go low high
where
go !low !high
| high <= low = return high
| otherwise = p mid >>= bool (go (mid + 1) high) (go low mid)
where
mid = low + unsafeShiftRL (high - low) 1
{-# INLINE lowerBoundM #-}
upperBoundM :: (Monad m) => Int -> Int -> (Int -> m Bool) -> m Int
upperBoundM low high p = do
flg <- p high
if flg
then return high
else subtract 1 <$!> lowerBoundM low high (fmap not.p)
{-# INLINE upperBoundM #-}
lowerBound :: Int -> Int -> (Int -> Bool) -> Int
lowerBound low high p = runIdentity (lowerBoundM low high (return . p))
{-# INLINE lowerBound #-}
upperBound :: Int -> Int -> (Int -> Bool) -> Int
upperBound low high p = runIdentity (upperBoundM low high (return . p))
{-# INLINE upperBound #-}
(.>>.) :: Bits i => i -> Int -> i
(.>>.) = unsafeShiftR
{-# INLINE (.>>.) #-}
(.<<.) :: Bits i => i -> Int -> i
(.<<.) = unsafeShiftL
{-# INLINE (.<<.) #-}
(.>>>.) :: Int -> Int -> Int
(.>>>.) = unsafeShiftRL
{-# INLINE (.>>>.) #-}
-------------------------------------------------------------------------------
type Parser a = BSC8.ByteString -> Maybe (a, BSC8.ByteString)
parseInt :: Parser Int
parseInt = fmap (second BSC8.tail) . BSC8.readInt
parseChar :: [Char] -> VU.Vector Char
parseChar = VU.fromList
parse1 :: IO Int
parse1 = readLn
parse2 :: IO (Int, Int)
parse2 = (\vec -> (vec VU.! 0, vec VU.! 1)) . VU.unfoldrN 2 parseInt <$> BSC8.getLine
parse3 :: IO (Int, Int, Int)
parse3 = (\vec -> (vec VU.! 0, vec VU.! 1, vec VU.! 2)) . VU.unfoldrN 3 parseInt <$> BSC8.getLine
parse4 :: IO (Int, Int, Int, Int)
parse4 = (\vec -> (vec VU.! 0, vec VU.! 1, vec VU.! 2, vec VU.! 3)) . VU.unfoldrN 4 parseInt <$> BSC8.getLine
parseM :: Int -> IO (VU.Vector Int)
parseM m = VU.unfoldrN m parseInt <$> BSC8.getLine
parseN :: Int -> IO (VU.Vector Int)
parseN n = VU.replicateM n parse1
parseNM :: Int -> Int -> IO (V.Vector (VU.Vector Int))
parseNM n m = V.replicateM n $ VU.unfoldrN m parseInt <$> BSC8.getLine
parseANBN :: Int -> IO (VU.Vector Int, VU.Vector Int)
parseANBN n = do
vectup <- VU.replicateM n $ (\vec -> (vec VU.! 0, vec VU.! 1)) . VU.unfoldr (BSC8.readInt . BSC8.dropWhile isSpace) <$> BSC8.getLine
return $ VU.unzip vectup
parseANBNCN :: Int -> IO (VU.Vector Int, VU.Vector Int, VU.Vector Int)
parseANBNCN n = do
vectup <- VU.replicateM n $ (\vec -> (vec VU.! 0, vec VU.! 1, vec VU.! 2)) . VU.unfoldr (BSC8.readInt . BSC8.dropWhile isSpace) <$> BSC8.getLine
return $ VU.unzip3 vectup
-------------------------------------------------------------------------------
modulus :: Num a => a
modulus = MOD
{-# INLINE modulus #-}
infixr 8 ^%
infixl 7 *%, /%
infixl 6 +%, -%
(+%) :: Int -> Int -> Int
(+%) (I# x#) (I# y#) = case x# +# y# of
r# -> I# (r# -# ((r# >=# MOD#) *# MOD#))
{-# INLINE (+%) #-}
(-%) :: Int -> Int -> Int
(-%) (I# x#) (I# y#) = case x# -# y# of
r# -> I# (r# +# ((r# <# 0#) *# MOD#))
{-# INLINE (-%) #-}
(*%) :: Int -> Int -> Int
(*%) (I# x#) (I# y#) = case timesWord# (int2Word# x#) (int2Word# y#) of
z# -> case timesWord2# z# im# of
(# q#, _ #) -> case minusWord# z# (timesWord# q# m#) of
v# | isTrue# (geWord# v# m#) -> I# (word2Int# (plusWord# v# m#))
| otherwise -> I# (word2Int# v#)
where
m# = int2Word# MOD#
im# = plusWord# (quotWord# 0xffffffffffffffff## m#) 1##
{-# INLINE (*%) #-}
(/%) :: Int -> Int -> Int
(/%) (I# x#) (I# y#) = go# y# MOD# 1# 0#
where
go# a# b# u# v#
| isTrue# (b# ># 0#) = case a# `quotInt#` b# of
q# -> go# b# (a# -# (q# *# b#)) v# (u# -# (q# *# v#))
| otherwise = I# ((x# *# (u# +# MOD#)) `remInt#` MOD#)
{-# INLINE (/%) #-}
(^%) :: Int -> Int -> Int
(^%) x n
| n > 0 = go 1 x n
| n == 0 = 1
| otherwise = go 1 (1 /% x) (-n)
where
go !acc !y !m
| m .&. 1 == 0 = go acc (y *% y) (unsafeShiftR m 1)
| m == 1 = acc *% y
| otherwise = go (acc *% y) (y *% y) (unsafeShiftR (m - 1) 1)
newtype Mint = Mint { getMint :: Int }
deriving newtype (Eq, Ord, Read, Show, Real)
mint :: Integral a => a -> Mint
mint x = fromIntegral $ mod (fromIntegral x) MOD
{-# INLINE mint #-}
instance Num Mint where
(+) = coerce (+%)
(-) = coerce (-%)
(*) = coerce (*%)
abs = id
signum = const (Mint 1)
fromInteger x = coerce @Int @Mint . fromInteger $ mod x modulus
instance Bounded Mint where
minBound = Mint 0
maxBound = Mint $ modulus - 1
instance Enum Mint where
toEnum = mint
fromEnum = coerce
instance Integral Mint where
quotRem x y = (x / y, x - x / y * y)
toInteger = coerce (toInteger @Int)
instance Fractional Mint where
(/) = coerce (/%)
fromRational q = fromInteger (numerator q) / fromInteger (denominator q)
newtype instance VU.Vector Mint = V_Mint (VU.Vector Int)
newtype instance VUM.MVector s Mint = MV_Mint (VUM.MVector s Int)
instance VU.Unbox Mint
instance VGM.MVector VUM.MVector Mint where
basicLength (MV_Mint v) = VGM.basicLength v
{-# INLINE basicLength #-}
basicUnsafeSlice i n (MV_Mint v) = MV_Mint $ VGM.basicUnsafeSlice i n v
{-# INLINE basicUnsafeSlice #-}
basicOverlaps (MV_Mint v1) (MV_Mint v2) = VGM.basicOverlaps v1 v2
{-# INLINE basicOverlaps #-}
basicUnsafeNew n = MV_Mint `fmap` VGM.basicUnsafeNew n
{-# INLINE basicUnsafeNew #-}
basicInitialize (MV_Mint v) = VGM.basicInitialize v
{-# INLINE basicInitialize #-}
basicUnsafeReplicate n x = MV_Mint `fmap` VGM.basicUnsafeReplicate n (coerce x)
{-# INLINE basicUnsafeReplicate #-}
basicUnsafeRead (MV_Mint v) i = coerce `fmap` VGM.basicUnsafeRead v i
{-# INLINE basicUnsafeRead #-}
basicUnsafeWrite (MV_Mint v) i x = VGM.basicUnsafeWrite v i (coerce x)
{-# INLINE basicUnsafeWrite #-}
basicClear (MV_Mint v) = VGM.basicClear v
{-# INLINE basicClear #-}
basicSet (MV_Mint v) x = VGM.basicSet v (coerce x)
{-# INLINE basicSet #-}
basicUnsafeCopy (MV_Mint v1) (MV_Mint v2) = VGM.basicUnsafeCopy v1 v2
{-# INLINE basicUnsafeCopy #-}
basicUnsafeMove (MV_Mint v1) (MV_Mint v2) = VGM.basicUnsafeMove v1 v2
{-# INLINE basicUnsafeMove #-}
basicUnsafeGrow (MV_Mint v) n = MV_Mint `fmap` VGM.basicUnsafeGrow v n
{-# INLINE basicUnsafeGrow #-}
instance VG.Vector VU.Vector Mint where
basicUnsafeFreeze (MV_Mint v) = V_Mint `fmap` VG.basicUnsafeFreeze v
{-# INLINE basicUnsafeFreeze #-}
basicUnsafeThaw (V_Mint v) = MV_Mint `fmap` VG.basicUnsafeThaw v
{-# INLINE basicUnsafeThaw #-}
basicLength (V_Mint v) = VG.basicLength v
{-# INLINE basicLength #-}
basicUnsafeSlice i n (V_Mint v) = V_Mint $ VG.basicUnsafeSlice i n v
{-# INLINE basicUnsafeSlice #-}
basicUnsafeIndexM (V_Mint v) i = coerce `fmap` VG.basicUnsafeIndexM v i
{-# INLINE basicUnsafeIndexM #-}
basicUnsafeCopy (MV_Mint mv) (V_Mint v) = VG.basicUnsafeCopy mv v
elemseq _ = seq
{-# INLINE elemseq #-}
-------------------------------------------------------------------------------
main :: IO ()
main = do
m <- parse1
as <- parseM m
let sumA = VU.sum as
let bs = VU.scanl1 (+) as
putStrLn $ bool "No" "Yes" $ VU.and $ VU.imap (\i a -> if i == 0 then True else 0 == mod (sumA - bs VU.! (i - 1)) (i + 1)) bs
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0