結果
問題 | No.774 tatyamと素数大富豪 |
ユーザー | こまる |
提出日時 | 2020-11-06 12:28:08 |
言語 | Haskell (9.8.2) |
結果 |
CE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 7,099 bytes |
コンパイル時間 | 179 ms |
コンパイル使用メモリ | 157,312 KB |
最終ジャッジ日時 | 2024-11-14 23:54:08 |
合計ジャッジ時間 | 671 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。(リジャッジ後のコンパイルエラーは公開されます)
ただし、clay言語の場合は開発者のデバッグのため、公開されます。
ただし、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:16: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. | 16 | import qualified GHC.Integer.GMP.Internals as GMP | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
ソースコード
{-# LANGUAGE BangPatterns #-} {-# LANGUAGE FlexibleInstances #-} {-# LANGUAGE TupleSections #-} import Control.Monad import Control.Monad.Fix import Control.Monad.State import Data.Bits import Data.Char import Data.Coerce import qualified Data.Foldable as F import Data.IORef import Data.Word import Unsafe.Coerce import qualified Data.ByteString.Char8 as BSC8 import qualified GHC.Integer.GMP.Internals as GMP import qualified Data.Vector.Fusion.Stream.Monadic as VFSM import qualified Data.Vector.Unboxed as VU import qualified Data.Vector.Unboxed.Mutable as VUM main :: IO () main = do n <- readLn :: IO Int xs <- radixSort <$> seqInput n ys <- VU.unsafeThaw xs ans <- newIORef (-1 :: Int) fix $ \loop -> do x <- newIORef (0 :: Int) rep n $ \i -> do item <- VUM.unsafeRead ys i if (item >= 10) then do modifyIORef' x (* 100) modifyIORef' x (+ item) else do modifyIORef' x (* 10) modifyIORef' x (+ item) item1 <- readIORef ans item2 <- readIORef x when (item1 < item2 && millerRabin item2) $ do when (item2 > item1) $ writeIORef ans item2 b <- VUM.nextPermutation ys when b loop print =<< readIORef ans millerRabin :: Int -> Bool millerRabin k | k <= 3 = k == 2 || k == 3 | even k = False | otherwise = mr k where mr :: Int -> Bool mr n | n < 2047 = loop [2] | n < 1373653 = loop [2,3] | n < 9080191 = loop [31,73] | n < 25326001 = loop [2,3,5] | n < 4759123141 = loop [2,7,61] | n < 1122004669633 = loop [2,13,23,1662803] | n < 2152302898747 = loop [2,3,5,7,11] | n < 3474749660383 = loop [2,3,5,7,11,13] | n < 341550071728321 = loop [2,3,5,7,11,13,17] | otherwise = loop [2,325,9375,28178,450775,9780504,1795265022] where !m = n - 1 !s = ctz m !d = m .>>. s loop :: [Int] -> Bool loop [] = True loop (a:as) | powModInt a d n /= 1 && allok = False | otherwise = loop as where allok = all (\r -> (powModInt a ((1 .<<. r) * d) n) /= m) $ [0..(s - 1)] radixSort64 :: VU.Vector Word64 -> VU.Vector Word64 radixSort64 vword = F.foldl' step vword [0,16,32,48] where mask k x = fromIntegral $ x .>>. k .&. 0xffff step v k = VU.create $ do pref <- VU.unsafeThaw . VU.prescanl' (+) 0 . VU.unsafeAccumulate (+) (VU.replicate 0x10000 0) $ VU.map ((, 1) . mask k) v res <- VUM.unsafeNew $ VU.length v VU.forM_ v $ \x -> do let !masked = mask k x i <- VUM.unsafeRead pref masked VUM.unsafeWrite pref masked $ i + 1 VUM.unsafeWrite res i x return res {-# INLINE radixSort64 #-} radixSort :: (VU.Unbox a, Word64Encode a) => VU.Vector a -> VU.Vector a radixSort = VU.map decode64 . radixSort64 . VU.map encode64 {-# INLINE radixSort #-} radixSortInt :: VU.Vector Int -> VU.Vector Int radixSortInt = unsafeCoerce . radixSort64 . unsafeCoerce radixSortNonNegative :: (VU.Unbox a, Word64Encode a) => VU.Vector a -> VU.Vector a radixSortNonNegative = VU.map decodeNonNegative64 . radixSort64 . VU.map encodeNonNegative64 {-# INLINE radixSortNonNegative #-} radixSort32 :: VU.Vector Word32 -> VU.Vector Word32 radixSort32 vec = F.foldl' step vec [0, 16] where mask k x = fromIntegral $ x .>>. k .&. 0xffff step v k = VU.create $ do pref <- VU.unsafeThaw . VU.prescanl' (+) 0 . VU.unsafeAccumulate (+) (VU.replicate 0x10000 0) $ VU.map ((, 1) . mask k) v res <- VUM.unsafeNew $ VU.length v VU.forM_ v $ \x -> do let !masked = mask k x i <- VUM.unsafeRead pref masked VUM.unsafeWrite pref masked $ i + 1 VUM.unsafeWrite res i x return res {-# INLINE radixSort32 #-} compress :: VU.Vector Int -> VU.Vector Int compress vec = VU.create $ do mvec <- VUM.unsafeNew (VU.length vec) VU.mapM_ (\(i, x) -> VUM.unsafeWrite mvec (x .&. 0xffffffff) i) . VU.postscanl' (\(!i, !x) y -> if x .>>. 32 == y .>>. 32 then (i, y) else (i + 1, y) ) (-1, -1) . radixSortInt $ VU.imap (\i x -> x .<<. 32 .|. i) vec return mvec {-# INLINE compress #-} class Word64Encode a where encode64 :: a -> Word64 decode64 :: Word64 -> a encodeNonNegative64 :: a -> Word64 encodeNonNegative64 = encode64 decodeNonNegative64 :: Word64 -> a decodeNonNegative64 = decode64 instance Word64Encode Int where encode64 x = unsafeCoerce $ x + 0x3fffffffffffffff decode64 x = unsafeCoerce x - 0x3fffffffffffffff encodeNonNegative64 = unsafeCoerce decodeNonNegative64 = unsafeCoerce instance Word64Encode (Int, Int) where encode64 (x, y) = unsafeCoerce $ (x + 0x3fffffff) .<<. 31 .|. (y + 0x3fffffff) decode64 xy = unsafeCoerce (x, y) where !x = xy .>>. 31 - 0x3fffffff !y = (xy .&. 0x7fffffff) - 0x3fffffff encodeNonNegative64 (x, y) = unsafeCoerce $ x .<<. 31 .|. y decodeNonNegative64 xy = unsafeCoerce (x, y) where !x = xy .>>. 31 !y = xy .&. 0x7fffffff instance Word64Encode (Int, Int, Int) where encode64 (x, y, z) = unsafeCoerce $ ((x + 0xfffff) .<<. 21 .|. (y + 0xfffff)) .<<. 21 .|. (z + 0xfffff) decode64 xyz = unsafeCoerce (x, y, z) where !x = xyz .>>. 42 - 0xfffff !y = (xyz .>>. 21 .&. 0x1fffff) - 0xfffff !z = xyz .&. 0x1fffff - 0xfffff encodeNonNegative64 (x, y, z) = unsafeCoerce $ (x .<<. 21 .|. y) .<<. 21 .|. z decodeNonNegative64 xyz = unsafeCoerce (x, y, z) where !x = xyz .>>. 42 !y = xyz .>>. 21 .&. 0x1fffff !z = xyz .&. 0x1fffff 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 #-} infixl 8 .<<., .>>. (.<<.) :: Bits b => b -> Int -> b (.<<.) = unsafeShiftL {-# INLINE (.<<.) #-} (.>>.) :: Bits b => b -> Int -> b (.>>.) = unsafeShiftR {-# INLINE (.>>.) #-} fi :: Int -> Integer fi = fromIntegral {-# INLINE fi #-} fI :: Integer -> Int fI = fromInteger {-# INLINE fI #-} ctz :: FiniteBits fb => fb -> Int ctz = countTrailingZeros {-# INLINE ctz #-} powModInt :: Int -> Int -> Int -> Int powModInt !a !n !mo = fI $ GMP.powModInteger (fi a) (fi n) (fi mo) {-# INLINE powModInt #-} 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 #-}