結果
問題 | No.50 おもちゃ箱 |
ユーザー | satonakatakumi |
提出日時 | 2021-08-21 15:41:25 |
言語 | Haskell (9.6.2) |
結果 |
RE
|
実行時間 | - |
コード長 | 3,563 bytes |
コンパイル時間 | 13,298 ms |
コンパイル使用メモリ | 243,404 KB |
実行使用メモリ | 7,828 KB |
最終ジャッジ日時 | 2023-08-05 09:06:43 |
合計ジャッジ時間 | 7,197 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge13 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | RE | - |
testcase_01 | RE | - |
testcase_02 | RE | - |
testcase_03 | RE | - |
testcase_04 | RE | - |
testcase_05 | RE | - |
testcase_06 | RE | - |
testcase_07 | RE | - |
testcase_08 | RE | - |
testcase_09 | RE | - |
testcase_10 | RE | - |
testcase_11 | RE | - |
testcase_12 | RE | - |
testcase_13 | RE | - |
testcase_14 | RE | - |
testcase_15 | RE | - |
testcase_16 | RE | - |
testcase_17 | RE | - |
testcase_18 | RE | - |
testcase_19 | RE | - |
testcase_20 | RE | - |
testcase_21 | RE | - |
testcase_22 | RE | - |
testcase_23 | RE | - |
testcase_24 | RE | - |
testcase_25 | RE | - |
testcase_26 | RE | - |
testcase_27 | RE | - |
testcase_28 | RE | - |
testcase_29 | RE | - |
testcase_30 | RE | - |
testcase_31 | RE | - |
testcase_32 | RE | - |
testcase_33 | RE | - |
testcase_34 | RE | - |
testcase_35 | RE | - |
testcase_36 | RE | - |
testcase_37 | RE | - |
testcase_38 | RE | - |
testcase_39 | RE | - |
testcase_40 | RE | - |
testcase_41 | RE | - |
コンパイルメッセージ
Loaded package environment from /home/judge/.ghc/x86_64-linux-9.6.1/environments/default [1 of 2] Compiling Main ( Main.hs, Main.o ) [2 of 2] Linking a.out
ソースコード
{-# LANGUAGE BangPatterns #-} {-# LANGUAGE TupleSections #-} {-# LANGUAGE TypeApplications #-} import Control.Monad import Control.Monad.Fix import Control.Monad.ST import Control.Monad.State import Data.Bits import Data.Bool import qualified Data.ByteString as BS import qualified Data.ByteString.Builder as BSB import qualified Data.ByteString.Char8 as BSC8 import qualified Data.ByteString.Lazy.Char8 as BSLC8 import qualified Data.ByteString.Unsafe as BSU import Data.Char import Data.Coerce import qualified Data.Foldable as F import Data.IORef import Data.Int import qualified Data.List as L import Data.STRef 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.Unboxed as VU import qualified Data.Vector.Unboxed.Mutable as VUM import Data.Word import qualified GHC.Integer.GMP.Internals as GMP import System.CPUTime import System.IO import Unsafe.Coerce inf :: Int inf = 1234567890 {-# INLINE inf #-} maxSize :: Int maxSize = 1 `unsafeShiftL` 10 {-# INLINE maxSize #-} main :: IO () main = do n <- readLn :: IO Int as <- seqInput n m <- readLn :: IO Int bs <- VU.reverse . bucketSort <$> seqInput m sum <- VUM.unsafeNew maxSize :: IO (VUM.IOVector Int) dp <- VUM.unsafeNew (11 * maxSize) :: IO (VUM.IOVector Int) rep (1 `unsafeShiftL` n) $ \i -> do VUM.unsafeWrite sum i 0 rep n $ \j -> when ((i `unsafeShiftR` j) .&. 1 /= 0) $ VUM.unsafeModify sum (+ as VU.! i) i rep m $ \ i -> rep (1 `unsafeShiftL` n) $ \j -> VUM.unsafeWrite dp (i * maxSize + j) inf VUM.unsafeWrite dp 0 0 rep m $ \i -> rep (1 `unsafeShiftL` n) $ \j -> do dpij <- VUM.unsafeRead dp (i * maxSize + j) VUM.unsafeWrite dp ((i + 1) * maxSize + j) dpij flip fix j $ \loop t -> do sumt <- VUM.unsafeRead sum t when (bs VU.! i >= sumt) $ do item <- succ <$> VUM.unsafeRead dp (i * maxSize + j `xor` t) VUM.unsafeModify dp (min item) ((i + 1) * maxSize + j) unless (t == 0) $ loop ((t - 1) .&. j) ans <- VUM.unsafeRead dp (m * maxSize + (1 `unsafeShiftL` n) - 1) if ans == inf then putStrLn "-1" else print ans return () type Parser a = StateT BSC8.ByteString Maybe a runParser :: Parser a -> BSC8.ByteString -> Maybe (a, BSC8.ByteString) runParser = runStateT {-# INLINE runParser #-} int :: Parser Int int = coerce $ BSC8.readInt . BSC8.dropWhile isSpace {-# INLINE int #-} seqInput :: Int -> IO (VU.Vector Int) seqInput n = VU.unfoldrN n (runParser int) <$> BSC8.getLine {-# INLINE seqInput #-} rep :: Monad m => Int -> (Int -> m ()) -> m () rep n = flip VFSM.mapM_ (stream 0 n) {-# INLINE rep #-} 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 #-} bucketSort :: VU.Vector Int -> VU.Vector Int bucketSort = VU.concatMap (uncurry $ flip VU.replicate) . VU.indexed . VU.unsafeAccumulate (+) (VU.replicate 21 0) . VU.map (,1) {-# INLINE bucketSort #-}