結果
| 問題 | No.50 おもちゃ箱 |
| ユーザー |
 こまる
|
| 提出日時 | 2020-10-22 00:52:18 |
| 言語 | Haskell (9.8.2) |
| 結果 |
CE
(最新)
AC
(最初)
|
| 実行時間 | - |
| コード長 | 16,592 bytes |
| コンパイル時間 | 301 ms |
| コンパイル使用メモリ | 158,336 KB |
| 最終ジャッジ日時 | 2024-11-14 23:52:19 |
| 合計ジャッジ時間 | 845 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
| ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
ソースコード
{-# LANGUAGE BangPatterns #-}
{-# LANGUAGE CPP #-}
{-# LANGUAGE FlexibleInstances #-}
{-# LANGUAGE LambdaCase #-}
{-# LANGUAGE MagicHash #-}
{-# LANGUAGE MultiWayIf #-}
{-# LANGUAGE NumericUnderscores #-}
{-# LANGUAGE OverloadedStrings #-}
{-# LANGUAGE RankNTypes #-}
{-# LANGUAGE RecordWildCards #-}
{-# LANGUAGE TupleSections #-}
{-# LANGUAGE TypeApplications #-}
{-# LANGUAGE UnboxedTuples #-}
import Control.Arrow
import Control.Monad
import Control.Monad.Fix
import Control.Monad.Identity
import Control.Monad.ST
import Control.Monad.State
import Data.Bits
import Data.Bool
import Data.Char
import Data.Coerce
import qualified Data.Complex as C
import qualified Data.Foldable as F
import Data.IORef
import qualified Data.List as L
import qualified Data.Maybe as M
import Data.STRef
import Data.Word
import GHC.Exts
import qualified System.IO as SysIO
import Unsafe.Coerce
import qualified Data.ByteString as BS
import qualified Data.ByteString.Char8 as BSC8
import qualified Data.ByteString.Unsafe as BSU
import Data.Map.Strict (Map)
import qualified Data.Map.Strict as Map
import Data.IntMap.Strict (IntMap)
import qualified Data.IntMap.Strict as IntMap
import qualified Data.Vector as V
import qualified Data.Vector.Mutable as VM
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.Unboxed as VU
import qualified Data.Vector.Unboxed.Mutable as VUM
import qualified GHC.Integer.GMP.Internals as GMP
-------------------------------------------------------------------------------
-- main
-------------------------------------------------------------------------------
inf :: Int
inf = 123456
{-# INLINE inf #-}
main :: IO ()
main = do
n <- readLn :: IO Int
as <- seqInput n
m <- readLn :: IO Int
bs' <- seqInput m
let bs = VU.reverse $ radixSortInt $ bs'
dp <- VUM.replicate (1 .<<. (11 :: Int)) inf
VUM.unsafeWrite dp 0 (0 :: Int)
rep (1 .<<. n) $ \i -> do
dpi <- VUM.unsafeRead dp i
when (dpi < m) $ do
rep (1 .<<. n) $ \j -> do
when (i .&. j == 0) $ do
s <- newIORef (0 :: Int)
rep n $ \k -> when (j .>>. k .&. 1 /= 0) $ modifyIORef' s (+ as VU.! k)
s' <- readIORef s
when (s' <= bs VU.! dpi) $ VUM.unsafeModify dp (min (dpi + 1)) (i .|. j)
ans <- VUM.unsafeRead dp (1 .<<. n - 1)
if ans == inf
then putStrLn "-1"
else print ans
-------------------------------------------------------------------------------
-- input
-------------------------------------------------------------------------------
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 #-}
int1 :: CParser Int
int1 = fmap (subtract 1) int
{-# INLINE int1 #-}
char :: CParser Char
char = coerce BSC8.uncons
{-# INLINE char #-}
byte :: CParser Word8
byte = coerce BS.uncons
{-# INLINE byte #-}
skipSpaces :: CParser ()
skipSpaces = modify' (BSC8.dropWhile isSpace)
{-# INLINE skipSpaces #-}
seqInput :: Int -> IO (VU.Vector Int)
seqInput n = VU.unfoldrN n (runCParser int) <$> BSC8.getLine
{-# INLINE seqInput #-}
parseN2 :: Int -> IO (VU.Vector (Int, Int))
parseN2 n = VU.unfoldrN n (runCParser $ (,) <$> int <*> int) <$> BSC8.getContents
{-# INLINE parseN2 #-}
parseN3 :: Int -> IO (VU.Vector (Int, Int, Int))
parseN3 n = VU.unfoldrN n (runCParser $ (,,) <$> int <*> int <*> int) <$> BSC8.getContents
{-# INLINE parseN3 #-}
parseN4 :: Int -> IO (VU.Vector (Int, Int, Int, Int))
parseN4 n = VU.unfoldrN n (runCParser $ (,,,) <$> int <*> int <*> int <*> int) <$> BSC8.getContents
{-# INLINE parseN4 #-}
parseN5 :: Int -> IO (VU.Vector (Int, Int, Int, Int, Int))
parseN5 n = VU.unfoldrN n (runCParser $ (,,,,) <$> int <*> int <*> int <*> int <*> int) <$> BSC8.getContents
{-# INLINE parseN5 #-}
parseANBN :: Int -> IO (VU.Vector Int, VU.Vector Int)
parseANBN n = VU.unzip . VU.unfoldrN n (runCParser $ (,) <$> int <*> int) <$> BSC8.getContents
{-# INLINE parseANBN #-}
parseANBNCN :: Int -> IO (VU.Vector Int, VU.Vector Int, VU.Vector Int)
parseANBNCN n = VU.unzip3 . VU.unfoldrN n (runCParser $ (,,) <$> int <*> int <*> int) <$> BSC8.getContents
{-# INLINE parseANBNCN #-}
type Query5 = (Int, Int, Int, Int, Int)
query5Parser :: CParser Query5
query5Parser = do
skipSpaces
t <- char
case t of
'0' -> (,,,,) 0 <$> int <*> int <*> int <*> int
_ -> (,,,,) 1 <$> int <*> int <*> pure 0 <*> pure 0
parseQ5 :: Int -> IO (VU.Vector Query5)
parseQ5 n = VU.unfoldrN n (runCParser query5Parser) <$> BSC8.getContents
{-# INLINE parseQ5 #-}
-------------------------------------------------------------------------------
-- utils
-------------------------------------------------------------------------------
powModInt :: Int -> Int -> Int -> Int
powModInt a n mo = fI $ GMP.powModInteger (fi a) (fi n) (fi mo)
recipModInt :: Int -> Int -> Int
recipModInt a mo = fI $ GMP.recipModInteger (fi a) (fi mo)
floorSqrt :: Int -> Int
floorSqrt = floor . sqrt . fromIntegral
floorLog2 :: Int -> Int
floorLog2 x = fromIntegral $ y .>>. 52 - 1023
where
y :: Word64
y = unsafeCoerce (fromIntegral x :: Double)
clz :: FiniteBits fb => fb -> Int
clz = countLeadingZeros
{-# INLINE clz #-}
ctz :: FiniteBits fb => fb -> Int
ctz = countTrailingZeros
{-# INLINE ctz #-}
ceilPow2 :: Int -> Int
ceilPow2 n
| n > 1 = (-1) .>>>. (clz (n - 1)) + 1
| otherwise = 1
floorPow2 :: Int -> Int
floorPow2 n
| n >= 1 = 1 .<<. (63 - (clz n))
| otherwise = 0
fi :: Int -> Integer
fi = fromIntegral
{-# INLINE fi #-}
fI :: Integer -> Int
fI = fromInteger
{-# INLINE fI #-}
infixl 8 .<<., .>>., .>>>.
infixl 6 .^.
(.<<.) :: Bits b => b -> Int -> b
(.<<.) = unsafeShiftL
{-# INLINE (.<<.) #-}
(.>>.) :: Bits b => b -> Int -> b
(.>>.) = unsafeShiftR
{-# INLINE (.>>.) #-}
(.>>>.) :: Int -> Int -> Int
(.>>>.) (I# x#) (I# i#) = I# (uncheckedIShiftRL# x# i#)
{-# INLINE (.>>>.) #-}
(.^.) :: Bits b => b -> b -> b
(.^.) = xor
{-# INLINE (.^.) #-}
encode32x2 :: Int -> Int -> Int
encode32x2 x y = x .<<. 32 .|. y
{-# INLINE encode32x2 #-}
decode32x2 :: Int -> (Int, Int)
decode32x2 xy =
let !x = xy .>>>. 32
!y = xy .&. 0xffffffff
in (x, y)
{-# INLINE decode32x2 #-}
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 #-}
rep' :: Monad m => Int -> (Int -> m ()) -> m ()
rep' n = flip VFSM.mapM_ (stream 0 (n + 1))
{-# INLINE rep' #-}
rep1 :: Monad m => Int -> (Int -> m ()) -> m ()
rep1 n = flip VFSM.mapM_ (stream 1 (n + 1))
{-# INLINE rep1 #-}
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 #-}
rev' :: Monad m => Int -> (Int -> m ()) -> m ()
rev' n = flip VFSM.mapM_ (streamR 0 (n + 1))
{-# INLINE rev' #-}
rev1 :: Monad m => Int -> (Int -> m ()) -> m ()
rev1 n = flip VFSM.mapM_ (streamR 1 (n + 1))
{-# INLINE rev1 #-}
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 #-}
repStep :: Monad m => Int -> Int -> Int -> (Int -> m ()) -> m ()
repStep l r d = flip VFSM.mapM_ (streamStep l r d)
{-# INLINE repStep #-}
repStep' :: Monad m => Int -> Int -> Int -> (Int -> m ()) -> m ()
repStep' l r d = flip VFSM.mapM_ (streamStep l (r + 1) d)
{-# INLINE repStep' #-}
memoFix :: Int -> ((Int -> a) -> Int -> a) -> Int -> a
memoFix n f = fix $ \memo -> (V.generate n (f memo) V.!)
memoFixMap :: Ord k => ((k -> State (Map.Map k a) a) -> k -> State (Map.Map k a) a) -> k -> a
memoFixMap f k = flip evalState Map.empty $ do
flip fix k $ \memo x -> do
gets (Map.lookup x) >>= \case
Just fx -> pure fx
Nothing -> f memo x >>= \fx -> modify' (Map.insert x fx) *> pure fx
memoFixIntMap :: ((Int -> State (IntMap.IntMap a) a) -> Int -> State (IntMap.IntMap a) a) -> Int -> a
memoFixIntMap f n = flip evalState IntMap.empty $ do
flip fix n $ \memo x -> do
gets (IntMap.lookup x) >>= \case
Just fx -> pure fx
Nothing -> f memo x >>= \fx -> modify' (IntMap.insert x fx) *> pure fx
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)]
smallPrimes :: Integral int => [int]
smallPrimes = 2 : [ n | n <- [3, 5 .. 46337], all ((> 0) . rem n) $ takeWhile (\x -> x * x <= n) smallPrimes]
{-# SPECIALIZE smallPrimes :: [Int] #-}
primeFactors :: Integral int => int -> [int]
primeFactors n | n < 2 = []
primeFactors n = go n smallPrimes
where
go n [] = [n]
go !n pps@(p : ps)
| n < p * p = [n]
| r > 0 = go n ps
| otherwise = p : go q pps
where
(q, r) = quotRem n p
{-# SPECIALIZE primeFactors :: Int -> [Int] #-}
getPrimeVector :: Int -> VU.Vector Int
getPrimeVector top = VU.filter (/= -1) . VU.imap (\i check -> if i == 0 then 2 else if check then i * 2 + 1 else -1) $! runST $ do
let m = (top - 1) .>>. 1
r = floor . sqrt . fromIntegral $ (top + 1)
sieve <- VU.unsafeThaw $ VU.replicate (m + 1) True
forM_ [1 .. r .>>. 1] $ \i -> do
isPrime <- VUM.unsafeRead sieve i
when isPrime $ do
forM_ [2 * i * (i + 1), 2 * i * (i + 2) + 1 .. m] $ \j -> do
VUM.unsafeWrite sieve j False
VU.unsafeFreeze sieve
nextRandF :: Int -> Int -> Int -> Int
nextRandF x n c = (x * x + c) `mod` n
factorRho :: Int -> [Int]
factorRho 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)
where
x = pollardRho n
y = if millerRabin x then x else pollardRho x
!s = ctz n
!d = n .>>. s
pollardRho :: Int -> Int
pollardRho k = runST $ do
x <- newSTRef (2 :: Int)
y <- newSTRef (2 :: Int)
d <- newSTRef (1 :: Int)
flip fix 1 $ \loop !c -> do
itemd <- readSTRef d
if itemd /= 1
then return itemd
else do
itemx <- readSTRef x
itemy <- readSTRef y
let
xx = nextRandF itemx k c
yy = nextRandF (nextRandF itemy k c) k c
dd = gcd (abs (xx - yy)) k
writeSTRef x xx
writeSTRef y yy
writeSTRef d dd
if dd /= k
then loop c
else do
writeSTRef x (2 :: Int)
writeSTRef y (2 :: Int)
writeSTRef d (1 :: Int)
loop (c + 2)
-------------------------------------------------------------------------------
-- radix sort
-------------------------------------------------------------------------------
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
radixSortInt :: VU.Vector Int -> VU.Vector Int
radixSortInt = unsafeCoerce . radixSort64 . unsafeCoerce
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 #-}
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 #-}