結果
問題 | No.2 素因数ゲーム |
ユーザー | こまる |
提出日時 | 2020-10-22 01:00:48 |
言語 | Haskell (9.10.1) |
結果 |
CE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 15,953 bytes |
コンパイル時間 | 224 ms |
コンパイル使用メモリ | 158,464 KB |
最終ジャッジ日時 | 2024-11-14 23:52:23 |
合計ジャッジ時間 | 589 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:38:1: error: [GHC-87110] Could not load module ‘Data.Map.Strict’. It is a member of the hidden package ‘containers-0.6.8’. Use -v to see a list of the files searched for. | 38 | import Data.Map.Strict (Map) | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ Main.hs:39:1: error: [GHC-87110] Could not load module ‘Data.Map.Strict’. It is a member of the hidden package ‘containers-0.6.8’. Use -v to see a list of the files searched for. | 39 | import qualified Data.Map.Strict as Map | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ Main.hs:40:1: error: [GHC-87110] Could not load module ‘Data.IntMap.Strict’. It is a member of the hidden package ‘containers-0.6.8’. Use -v to see a list of the files searched for. | 40 | import Data.IntMap.Strict (IntMap) | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ Main.hs:41:1: error: [GHC-87110] Could not load module ‘Data.IntMap.Strict’. It is a member of the hidden package ‘containers-0.6.8’. Use -v to see a list of the files searched for. | 41 | import qualified Data.IntMap.Strict as IntMap | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ Main.hs:49: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. | 49 | import qualified GHC.Integer.GMP.Internals as GMP | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
ソースコード
LANGUAGELANGUAGELANGUAGELANGUAGELANGUAGELANGUAGELANGUAGELANGUAGELANGUAGELANGUAGELANGUAGELANGUAGELANGUAGEimportControl.ArrowimportControl.MonadimportControl.Monad.FiximportControl.Monad.IdentityimportControl.Monad.STimportControl.Monad.StateimportData.BitsimportData.BoolimportData.CharimportData.CoerceimportqualifiedData.ComplexasCimportqualifiedData.FoldableasFimportData.IORefimportqualifiedData.ListasLimportqualifiedData.MaybeasMimportData.STRefimportData.WordimportGHC.ExtsimportqualifiedSystem.IOasSysIOimportUnsafe.CoerceimportqualifiedData.ByteStringasBSimportqualifiedData.ByteString.CharasBSCimportqualifiedData.ByteString.UnsafeasBSUimportData.Map.StrictMapimportqualifiedData.Map.StrictasMapimportData.IntMap.StrictIntMapimportqualifiedData.IntMap.StrictasIntMapimportqualifiedData.VectorasVimportqualifiedData.Vector.MutableasVMimportqualifiedData.Vector.Fusion.Stream.MonadicasVFSMimportqualifiedData.Vector.GenericasVGimportqualifiedData.Vector.Generic.MutableasVGMimportqualifiedData.Vector.UnboxedasVUimportqualifiedData.Vector.Unboxed.MutableasVUMimportqualifiedGHC.Integer.GMP.InternalsasGMP--------------------------------------------------------------------------------- main-------------------------------------------------------------------------------main::IO()main = readLn >>= putStrLn . bool "Alice" "Bob" . (== 0) . L.foldl1' xor . map length . L.group . factorRho--------------------------------------------------------------------------------- input-------------------------------------------------------------------------------type CParser a = StateT BSC8.ByteString Maybe arunCParser::CParsera->BSC8ByteString->MaybeaBSC8ByteStringrunCParser = runStateTINLINEint::CParserIntint = coerce $ BSC8.readInt . BSC8.dropWhile isSpaceINLINEint1::CParserIntint1 = fmap (subtract 1) intINLINEchar::CParserCharchar = coerce BSC8.unconsINLINEbyte::CParserWord8byte = coerce BS.unconsINLINEskipSpaces::CParser()skipSpaces = modify' (BSC8.dropWhile isSpace)INLINEseqInput::Int->IOVUVectorIntseqInput n = VU.unfoldrN n (runCParser int) <$> BSC8.getLineINLINEparseN2::Int->IOVUVectorIntIntparseN2 n = VU.unfoldrN n (runCParser $ (,) <$> int <*> int) <$> BSC8.getContentsINLINEparseN3::Int->IOVUVectorIntIntIntparseN3 n = VU.unfoldrN n (runCParser $ (,,) <$> int <*> int <*> int) <$> BSC8.getContentsINLINEparseN4::Int->IOVUVectorIntIntIntIntparseN4 n = VU.unfoldrN n (runCParser $ (,,,) <$> int <*> int <*> int <*> int) <$> BSC8.getContentsINLINEparseN5::Int->IOVUVectorIntIntIntIntIntparseN5 n = VU.unfoldrN n (runCParser $ (,,,,) <$> int <*> int <*> int <*> int <*> int) <$> BSC8.getContentsINLINEparseANBN::Int->IOVUVectorIntVUVectorIntparseANBN n = VU.unzip . VU.unfoldrN n (runCParser $ (,) <$> int <*> int) <$> BSC8.getContentsINLINEparseANBNCN::Int->IOVUVectorIntVUVectorIntVUVectorIntparseANBNCN n = VU.unzip3 . VU.unfoldrN n (runCParser $ (,,) <$> int <*> int <*> int) <$> BSC8.getContentsINLINEtype Query5 = (Int, Int, Int, Int, Int)query5Parser::CParserQuery5query5Parser = doskipSpacest <- charcase t of'0' -> (,,,,) 0 <$> int <*> int <*> int <*> int_ -> (,,,,) 1 <$> int <*> int <*> pure 0 <*> pure 0parseQ5::Int->IOVUVectorQuery5parseQ5 n = VU.unfoldrN n (runCParser query5Parser) <$> BSC8.getContentsINLINE--------------------------------------------------------------------------------- utils-------------------------------------------------------------------------------powModInt::Int->Int->Int->IntpowModInt a n mo = fI $ GMP.powModInteger (fi a) (fi n) (fi mo)recipModInt::Int->Int->IntrecipModInt a mo = fI $ GMP.recipModInteger (fi a) (fi mo)floorSqrt::Int->IntfloorSqrt = floor . sqrt . fromIntegralfloorLog2::Int->IntfloorLog2 x = fromIntegral $ y .>>. 52 - 1023wherey::Word64y = unsafeCoerce (fromIntegral x :: Double)clz::FiniteBitsfb=>fb->Intclz = countLeadingZerosINLINEctz::FiniteBitsfb=>fb->Intctz = countTrailingZerosINLINEceilPow2::Int->IntceilPow2 n| n > 1 = (-1) .>>>. (clz (n - 1)) + 1| otherwise = 1floorPow2::Int->IntfloorPow2 n| n >= 1 = 1 .<<. (63 - (clz n))| otherwise = 0fi::Int->Integerfi = fromIntegralINLINEfI::Integer->IntfI = fromIntegerINLINEinfixl 8 .<<., .>>., .>>>.infixl 6 .^.(.<<.)::Bitsb=>b->Int->b(.<<.) = unsafeShiftLINLINE(.>>.)::Bitsb=>b->Int->b(.>>.) = unsafeShiftRINLINE(.>>>.)::Int->Int->Int(.>>>.) (I# x#) (I# i#) = I# (uncheckedIShiftRL# x# i#)INLINE(.^.) :: Bits b => b -> b -> b(.^.) = xorINLINEencode32x2::Int->Int->Intencode32x2 x y = x .<<. 32 .|. yINLINEdecode32x2::Int->IntIntdecode32x2 xy =let !x = xy .>>>. 32!y = xy .&. 0xffffffffin (x, y)INLINEstream::Monadm=>Int->Int->VFSMStreammIntstream !l !r = VFSM.Stream step lwherestep x| x < r = return $ VFSM.Yield x (x + 1)| otherwise = return $ VFSM.DoneINLINEINLINErep::Monadm=>Int->Int->m()->m()rep n = flip VFSM.mapM_ (stream 0 n)INLINErep'::Monadm=>Int->Int->m()->m()rep' n = flip VFSM.mapM_ (stream 0 (n + 1))INLINErep1::Monadm=>Int->Int->m()->m()rep1 n = flip VFSM.mapM_ (stream 1 (n + 1))INLINEstreamR::Monadm=>Int->Int->VFSMStreammIntstreamR !l !r = VFSM.Stream step (r - 1)wherestep x| x >= l = return $ VFSM.Yield x (x - 1)| otherwise = return $ VFSM.DoneINLINEINLINErev::Monadm=>Int->Int->m()->m()rev n = flip VFSM.mapM_ (streamR 0 n)INLINErev'::Monadm=>Int->Int->m()->m()rev' n = flip VFSM.mapM_ (streamR 0 (n + 1))INLINErev1::Monadm=>Int->Int->m()->m()rev1 n = flip VFSM.mapM_ (streamR 1 (n + 1))INLINEstreamStep::Monadm=>Int->Int->Int->VFSMStreammIntstreamStep !l !r !d = VFSM.Stream step lwherestep x| x < r = return $ VFSM.Yield x (x + d)| otherwise = return $ VFSM.DoneINLINEINLINErepStep::Monadm=>Int->Int->Int->Int->m()->m()repStep l r d = flip VFSM.mapM_ (streamStep l r d)INLINErepStep'::Monadm=>Int->Int->Int->Int->m()->m()repStep' l r d = flip VFSM.mapM_ (streamStep l (r + 1) d)INLINEmemoFix::Int->Int->a->Int->a->Int->amemoFix n f = fix $ \memo -> (V.generate n (f memo) V.!)memoFixMap::Ordk=>k->StateMapMapkaa->k->StateMapMapkaa->k->amemoFixMap f k = flip evalState Map.empty $ doflip fix k $ \memo x -> dogets (Map.lookup x) >>= \caseJust fx -> pure fxNothing -> f memo x >>= \fx -> modify' (Map.insert x fx) *> pure fxmemoFixIntMap::Int->StateIntMapIntMapaa->Int->StateIntMapIntMapaa->Int->amemoFixIntMap f n = flip evalState IntMap.empty $ doflip fix n $ \memo x -> dogets (IntMap.lookup x) >>= \caseJust fx -> pure fxNothing -> f memo x >>= \fx -> modify' (IntMap.insert x fx) *> pure fxmillerRabin::Int->BoolmillerRabin k| k <= 3 = k == 2 || k == 3| even k = False| otherwise = mr kwheremr::Int->Boolmr 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 .>>. sloop::Int->Boolloop [] = Trueloop (a:as)| powModInt a d n /= 1 && allok = False| otherwise = loop aswhere allok = all (\r -> (powModInt a ((1 .<<. r) * d) n) /= m) [0..(s - 1)]smallPrimes::Integralint=>intsmallPrimes = 2 : [ n | n <- [3, 5 .. 46337], all ((> 0) . rem n) $ takeWhile (\x -> x * x <= n) smallPrimes]primeFactors::Integralint=>int->intprimeFactors n | n < 2 = []primeFactors n = go n smallPrimeswherego n [] = [n]go !n pps@(p : ps)| n < p * p = [n]| r > 0 = go n ps| otherwise = p : go q ppswhere(q, r) = quotRem n pgetPrimeVector::Int->VUVectorIntgetPrimeVector top = VU.filter (/= -1) . VU.imap (\i check -> if i == 0 then 2 else if check then i * 2 + 1 else -1) $! runST $ dolet m = (top - 1) .>>. 1r = floor . sqrt . fromIntegral $ (top + 1)sieve <- VU.unsafeThaw $ VU.replicate (m + 1) TrueforM_ [1 .. r .>>. 1] $ \i -> doisPrime <- VUM.unsafeRead sieve iwhen isPrime $ doforM_ [2 * i * (i + 1), 2 * i * (i + 2) + 1 .. m] $ \j -> doVUM.unsafeWrite sieve j FalseVU.unsafeFreeze sievenextRandF::Int->Int->Int->IntnextRandF x n c = (x * x + c) `mod` nfactorRho::Int->IntfactorRho n| n <= 1 = []| even n = replicate s 2 ++ factorRho d| n `mod` 3 == 0 = 3 : factorRho (n `div` 3)| n `mod` 5 == 0 = 5 : factorRho (n `div` 5)| n `mod` 7 == 0 = 7 : factorRho (n `div` 7)| n `mod` 11 == 0 = 11 : factorRho (n `div` 11)| n `mod` 13 == 0 = 13 : factorRho (n `div` 13)| n `mod` 17 == 0 = 17 : factorRho (n `div` 17)| n `mod` 19 == 0 = 19 : factorRho (n `div` 19)| n `mod` 23 == 0 = 23 : factorRho (n `div` 23)| millerRabin n = [n]| otherwise = y : factorRho (n `div` y)wherex = pollardRho ny = if millerRabin x then x else pollardRho x!s = ctz n!d = n .>>. spollardRho::Int->IntpollardRho k = runST $ dox <- newSTRef (2 :: Int)y <- newSTRef (2 :: Int)d <- newSTRef (1 :: Int)flip fix 1 $ \loop !c -> doitemd <- readSTRef dif itemd /= 1then return itemdelse doitemx <- readSTRef xitemy <- readSTRef yletxx = nextRandF itemx k cyy = nextRandF (nextRandF itemy k c) k cdd = gcd (abs (xx - yy)) kwriteSTRef x xxwriteSTRef y yywriteSTRef d ddif dd /= kthen loop celse dowriteSTRef x (2 :: Int)writeSTRef y (2 :: Int)writeSTRef d (1 :: Int)loop (c + 2)--------------------------------------------------------------------------------- radix sort-------------------------------------------------------------------------------classWordEncodeawhereencode64::a->Word64decode64::Word64->aencodeNonNegative64::a->Word64encodeNonNegative64 = encode64decodeNonNegative64::Word64->adecodeNonNegative64 = decode64instanceWord64EncodeIntwhereencode64 x = unsafeCoerce $ x + 0x3fffffffffffffffdecode64 x = unsafeCoerce x - 0x3fffffffffffffffencodeNonNegative64 = unsafeCoercedecodeNonNegative64 = unsafeCoerceinstanceWord64EncodeIntIntwhereencode64 (x, y) = unsafeCoerce$ (x + 0x3fffffff) .<<. 31 .|. (y + 0x3fffffff)decode64 xy = unsafeCoerce (x, y)where!x = xy .>>. 31 - 0x3fffffff!y = (xy .&. 0x7fffffff) - 0x3fffffffencodeNonNegative64 (x, y) = unsafeCoerce $ x .<<. 31 .|. ydecodeNonNegative64 xy = unsafeCoerce (x, y)where!x = xy .>>. 31!y = xy .&. 0x7fffffffinstanceWord64EncodeIntIntIntwhereencode64 (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 - 0xfffffencodeNonNegative64 (x, y, z) = unsafeCoerce $ (x .<<. 21 .|. y) .<<. 21 .|. zdecodeNonNegative64 xyz = unsafeCoerce (x, y, z)where!x = xyz .>>. 42!y = xyz .>>. 21 .&. 0x1fffff!z = xyz .&. 0x1fffffradixSortInt::VUVectorInt->VUVectorIntradixSortInt = unsafeCoerce . radixSort64 . unsafeCoerceradixSort64::VUVectorWord64->VUVectorWord64radixSort64 vword = F.foldl' step vword [0,16,32,48]wheremask k x = fromIntegral $ x .>>. k .&. 0xffffstep v k = VU.create $ dopref <- VU.unsafeThaw. VU.prescanl' (+) 0. VU.unsafeAccumulate (+) (VU.replicate 0x10000 0)$ VU.map ((, 1) . mask k) vres <- VUM.unsafeNew $ VU.length vVU.forM_ v $ \x -> dolet !masked = mask k xi <- VUM.unsafeRead pref maskedVUM.unsafeWrite pref masked $ i + 1VUM.unsafeWrite res i xreturn resINLINEradixSort::VUUnboxaWord64Encodea=>VUVectora->VUVectoraradixSort = VU.map decode64 . radixSort64 . VU.map encode64INLINEradixSortNonNegative::VUUnboxaWord64Encodea=>VUVectora->VUVectoraradixSortNonNegative= VU.map decodeNonNegative64 . radixSort64 . VU.map encodeNonNegative64INLINEradixSort32::VUVectorWord32->VUVectorWord32radixSort32 vec = F.foldl' step vec [0, 16]wheremask k x = fromIntegral $ x .>>. k .&. 0xffffstep v k = VU.create $ dopref <- VU.unsafeThaw. VU.prescanl' (+) 0. VU.unsafeAccumulate (+) (VU.replicate 0x10000 0)$ VU.map ((, 1) . mask k) vres <- VUM.unsafeNew $ VU.length vVU.forM_ v $ \x -> dolet !masked = mask k xi <- VUM.unsafeRead pref maskedVUM.unsafeWrite pref masked $ i + 1VUM.unsafeWrite res i xreturn resINLINEcompress::VUVectorInt->VUVectorIntcompress vec = VU.create $ domvec <- VUM.unsafeNew (VU.length vec)VU.mapM_ (\(i, x) -> VUM.unsafeWrite mvec (x .&. 0xffffffff) i). VU.postscanl' (\(!i, !x) y ->if x .>>. 32 == y .>>. 32then (i, y)else (i + 1, y)) (-1, -1). radixSortInt$ VU.imap (\i x -> x .<<. 32 .|. i) vecreturn mvecINLINE