結果
問題 | No.130 XOR Minimax |
ユーザー |
|
提出日時 | 2020-12-06 21:38:17 |
言語 | Haskell (9.10.1) |
結果 |
CE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 19,381 bytes |
コンパイル時間 | 279 ms |
コンパイル使用メモリ | 156,800 KB |
最終ジャッジ日時 | 2024-11-14 23:56:30 |
合計ジャッジ時間 | 1,288 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。(リジャッジ後のコンパイルエラーは公開されます)
ただし、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:26: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. | 26 | import qualified GHC.Integer.GMP.Internals as GMP | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
ソースコード
LANGUAGELANGUAGELANGUAGELANGUAGELANGUAGELANGUAGELANGUAGEimportControl.Monad.ContimportControl.Monad.STimportControl.Monad.StateimportData.BitsimportData.CharimportData.CoerceimportqualifiedData.FoldableasFimportData.IntimportData.IORefimportData.MaybeimportData.WordimportGHC.ExtsimportSystem.IOimportUnsafe.CoerceimportqualifiedData.ByteStringasBSimportqualifiedData.ByteString.BuilderasBSBimportqualifiedData.ByteString.CharasBSCimportqualifiedGHC.Integer.GMP.InternalsasGMPimportqualifiedData.Vector.Fusion.Stream.MonadicasVFSMimportqualifiedData.Vector.GenericasVGimportqualifiedData.Vector.UnboxedasVUimportqualifiedData.Vector.Unboxed.MutableasVUMmain::IO()main = don <- readLn :: IO Inta <- radixSortInt <$> seqInput nprint =<< solver a 0 n 30solver::VUVectorInt->Int->Int->Int->IOIntsolver a l r k| r - l < 1 = return $ 1 .<<. 30| k < 0 = return 0| otherwise = doxRef <- newIORef (0 :: Int)nrRef <- newIORef (r :: Int)withBreakIO $ \break -> range (l + 1) (r - 1) $ \i -> doletitem1 = (a VU.! i) .&. (1 .<<. k)item2 = (a VU.! (i - 1)) .&. (1 .<<. k)when (item1 /= item2) $ doliftIO $ writeIORef xRef (1 .<<. k)liftIO $ writeIORef nrRef ibreak()x <- readIORef xRefnr <- readIORef nrRefmin1 <- solver a l nr (k - 1)min2 <- solver a nr r (k - 1)return $ x + min min1 min2--------------------------------------------------------------------------------- radix sort-------------------------------------------------------------------------------radixSort64::VUVectorWord64->VUVectorWord64radixSort64 vword = F.foldl' step vword ([0,16,32,48] :: [Int])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 encode64INLINEradixSortInt::VUVectorInt->VUVectorIntradixSortInt = unsafeCoerce . radixSort64 . unsafeCoerceradixSortNonNegative::VUUnboxaWord64Encodea=>VUVectora->VUVectoraradixSortNonNegative = VU.map decodeNonNegative64 . radixSort64 . VU.map encodeNonNegative64INLINEradixSort32::VUVectorWord32->VUVectorWord32radixSort32 vec = F.foldl' step vec ([0, 16] :: [Int])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 mvecINLINEclassWordEncodeawhereencode64::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 .&. 0x1fffff--------------------------------------------------------------------------------- for-------------------------------------------------------------------------------rep::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)INLINErep1'::Monadm=>Int->Int->m()->m()rep1' n = flip VFSM.mapM_ (stream 1 (n + 1))INLINErev::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)INLINErev1'::Monadm=>Int->Int->m()->m()rev1' n = flip VFSM.mapM_ (streamR 1 (n + 1))INLINErange::Monadm=>Int->Int->Int->m()->m()range l r = flip VFSM.mapM_ (stream l (r + 1))INLINErangeR::Monadm=>Int->Int->Int->m()->m()rangeR r l = flip VFSM.mapM_ (streamR l (r + 1))INLINEforStep::Monadm=>Int->Int->Int->Int->m()->m()forStep l r d = flip VFSM.mapM_ (streamStep l r d)INLINEforStepR::Monadm=>Int->Int->Int->Int->m()->m()forStepR r l d = flip VFSM.mapM_ (streamStepR l r d)INLINEforP::Monadm=>Int->Int->m()->m()forP p = flip VFSM.mapM_ (streamG 2 p (^) 2 (+) 1)INLINEforG::Monadm=>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)INLINEforRG::Monadm=>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)INLINEstream::Monadm=>Int->Int->VFSMStreammIntstream !l !r = VFSM.Stream step lwherestep x| x < r = return $ VFSM.Yield x (x + 1)| otherwise = return VFSM.DoneINLINEINLINEstreamR::Monadm=>Int->Int->VFSMStreammIntstreamR !l !r = VFSM.Stream step (r - 1)wherestep x| x >= l = return $ VFSM.Yield x (x - 1)| otherwise = return VFSM.DoneINLINEINLINEstreamStep::Monadm=>Int->Int->Int->VFSMStreammIntstreamStep !l !r !d = VFSM.Stream step lwherestep x| x <= r = return $ VFSM.Yield x (x + d)| otherwise = return VFSM.DoneINLINEINLINEstreamStepR::Monadm=>Int->Int->Int->VFSMStreammIntstreamStepR !l !r !d = VFSM.Stream step rwherestep x| x >= l = return $ VFSM.Yield x (x - d)| otherwise = return VFSM.DoneINLINEINLINEstreamG::Monadm=>Int->Int->Int->Int->Int->Int->Int->Int->Int->Int->VFSMStreammIntstreamG !l !r !f !p !g !d = VFSM.Stream step lwherestep x| f x p <= r = return $ VFSM.Yield x (g x d)| otherwise = return VFSM.DoneINLINEINLINEstreamRG::Monadm=>Int->Int->Int->Int->Int->Int->Int->Int->Int->Int->VFSMStreammIntstreamRG !r !l !f !p !g !d = VFSM.Stream step rwherestep x| f x p >= l = return $ VFSM.Yield x (g x d)| otherwise = return VFSM.DoneINLINEINLINEwithBreakIO::r->ContTrIOb->ContTrIOr->IOrwithBreakIO = flip runContT pure . callCCINLINEwithBreakST::r->ContTrSTsb->ContTrSTsr->STsrwithBreakST = flip runContT pure . callCCINLINE--------------------------------------------------------------------------------- util-------------------------------------------------------------------------------fi::Int->Integerfi = fromIntegralINLINEfI::Integer->IntfI = fromIntegerINLINEpowModInt::Int->Int->Int->IntpowModInt a b c = fI $ GMP.powModInteger (fi a) (fi b) (fi c)INLINErecipModInt::Int->Int->IntrecipModInt a m = fI $ GMP.recipModInteger (fi a) (fi m)INLINEinfixl 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(.^.) = xorINLINEclz::FiniteBitsfb=>fb->Intclz = countLeadingZerosINLINEctz::FiniteBitsfb=>fb->Intctz = countTrailingZerosINLINEencode32x2::Int->Int->Intencode32x2 x y = x .<<. 32 .|. yINLINEdecode32x2::Int->IntIntdecode32x2 xy =let !x = xy .>>>. 32!y = xy .&. 0xffffffffin (x, y)INLINEceilPow2::Int->IntceilPow2 n| n > 1 = (-1) .>>>. clz (n - 1) + 1| otherwise = 1INLINEfloorPow2::Int->IntfloorPow2 n| n >= 1 = 1 .<<. (63 - clz n)| otherwise = 0INLINEbitReverse::Int->IntbitReverse= unsafeCoerce. step 32 0xffffffff00000000 0x00000000ffffffff. step 16 0xffff0000ffff0000 0x0000ffff0000ffff. step 08 0xff00ff00ff00ff00 0x00ff00ff00ff00ff. step 04 0xf0f0f0f0f0f0f0f0 0x0f0f0f0f0f0f0f0f. step 02 0xcccccccccccccccc 0x3333333333333333. step 01 0xaaaaaaaaaaaaaaaa 0x5555555555555555. unsafeCoercewherestep::Int->Word64->Word64->Word64->Word64step i ml mr = \ !x -> (x .&. ml) .>>. i .|. (x .&. mr) .<<. iINLINEctzceilpow2::Int->Intctzceilpow2 = countTrailingZeros . ceilPow2INLINE--------------------------------------------------------------------------------- input output-------------------------------------------------------------------------------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.getLineINLINEparseN1::Int->IOVUVectorIntparseN1 n = VU.unfoldrN n (runCParser int) <$> BSC8.getContentsINLINEparseN2::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 Query3 = (Int, Int, Int)query3Parser::CParserQuery3query3Parser = doskipSpacest <- charcase t of'0' -> (,,) 0 <$> int <*> int_ -> (,,) 1 <$> int <*> pure 0parseQ3::Int->IOVUVectorQuery3parseQ3 n = VU.unfoldrN n (runCParser query3Parser) <$> 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.getContentsINLINEreadInt::BSC8ByteString->IntreadInt = fst . fromJust . BSC8.readIntINLINEgetInt::IOIntgetInt = readInt <$> BSC8.getLineINLINEreadIntList::BSC8ByteString->IntreadIntList = map readInt . BSC8.wordsINLINEgetIntList::IOIntgetIntList = readIntList <$> BSC8.getLineINLINEreadInteger::BSC8ByteString->IntegerreadInteger = fst . fromJust . BSC8.readIntegerINLINEgetInteger::IOIntegergetInteger = readInteger <$> BSC8.getLineINLINEreadIntegerList::BSC8ByteString->IntegerreadIntegerList = map readInteger . BSC8.wordsINLINEgetIntegerList::IOIntegergetIntegerList = readIntegerList <$> BSC8.getLineINLINEclassShowAsBuilderawhereshowAsBuilder::a->BSBBuilderdefault showAsBuilder :: (Show a) => a -> BSB.BuildershowAsBuilder = BSB.string8 . showinstanceShowAsBuilderIntwhereshowAsBuilder = BSB.intDecINLINEinstanceShowAsBuilderInt8whereshowAsBuilder = BSB.int8DecINLINEinstanceShowAsBuilderInt16whereshowAsBuilder = BSB.int16DecINLINEinstanceShowAsBuilderInt32whereshowAsBuilder = BSB.int32DecINLINEinstanceShowAsBuilderInt64whereshowAsBuilder = BSB.int64DecINLINEinstanceShowAsBuilderWord8whereshowAsBuilder = BSB.word8DecINLINEinstanceShowAsBuilderWord16whereshowAsBuilder = BSB.word16DecINLINEinstanceShowAsBuilderWord32whereshowAsBuilder = BSB.word32DecINLINEinstanceShowAsBuilderWord64whereshowAsBuilder = BSB.word64DecINLINEinstanceShowAsBuilderIntegerwhereshowAsBuilder = BSB.integerDecINLINEinstanceShowAsBuilderFloatwhereshowAsBuilder = BSB.floatDecINLINEinstanceShowAsBuilderDoublewhereshowAsBuilder = BSB.doubleDecINLINEinstanceShowAsBuilderaVGVectorva=>ShowAsBuildervawhereshowAsBuilder = v2BSpcSepputBuilder::BSBBuilder->IO()putBuilder = BSB.hPutBuilder stdoutINLINEprintVecInLines::VGVectorvaShowAsBuildera=>va->IO()printVecInLines = putBuilder . v2BLinesINLINEprintVecInSpcSepLn::VGVectorvaShowAsBuildera=>va->IO()printVecInSpcSepLn = putBuilder . v2BSpcSepLnINLINEv2BSpcSepLn::VGVectorvaShowAsBuildera=>va->BSBBuilderv2BSpcSepLn = v2BSpcSepLnWith showAsBuilderINLINEv2BSpcSep::VGVectorvaShowAsBuildera=>va->BSBBuilderv2BSpcSep = v2BSpcSepWith showAsBuilderINLINEv2BConcat::VGVectorvaShowAsBuildera=>va->BSBBuilderv2BConcat = v2BConcatWith showAsBuilderINLINEv2BLines::VGVectorvaShowAsBuildera=>va->BSBBuilderv2BLines = v2BLinesWith showAsBuilderINLINEv2BSpcSepLnWith::VGVectorva=>a->BSBBuilder->va->BSBBuilderv2BSpcSepLnWith = v2BSpcSepPostfWith "\n"INLINEv2BSpcSepWith::VGVectorva=>a->BSBBuilder->va->BSBBuilderv2BSpcSepWith = v2BSpcSepPostfWith ""INLINEv2BConcatWith::VGVectorva=>a->BSBBuilder->va->BSBBuilderv2BConcatWith showFct = VG.foldr ((<>) . showFct) memptyINLINEv2BLinesWith::VGVectorva=>a->BSBBuilder->va->BSBBuilderv2BLinesWith showFct = VG.foldr (\a -> (showFct a <>) . (BSB.char7 '\n' <>)) memptyINLINEv2BSpcSepPostf::VGVectorvaShowAsBuildera=>BSByteString->va->BSBBuilderv2BSpcSepPostf = (`v2BSpcSepPostfWith` showAsBuilder)INLINEv2BSpcSepPostfWith::VGVectorva=>BSByteString->a->BSBBuilder->va->BSBBuilderv2BSpcSepPostfWith = vecToBuilder "" " "INLINEvecToBuilder::VGVectorva=>BSByteString->BSByteString->BSByteString->a->BSBBuilder->va->BSBBuildervecToBuilder !prefix !separator !postfix = vecToBuilder_ (BSB.byteString prefix) (BSB.byteString separator) (BSB.byteString postfix)INLINEvecToBuilder_::VGVectorva=>BSBBuilder->BSBBuilder->BSBBuilder->a->BSBBuilder->va->BSBBuildervecToBuilder_ !prefix !separator !postfix showFct vec = prefix <> VG.foldr (\a rest !prefx -> prefx <> (showFct a <> rest separator)) (const postfix)vec memptyINLINE