結果
問題 | No.4 おもりと天秤 |
ユーザー | こまる |
提出日時 | 2020-10-18 23:04:59 |
言語 | Haskell (9.8.2) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,990 bytes |
コンパイル時間 | 1,240 ms |
コンパイル使用メモリ | 198,768 KB |
実行使用メモリ | 7,592 KB |
最終ジャッジ日時 | 2023-09-28 12:09:22 |
合計ジャッジ時間 | 2,459 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge14 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 3 ms
7,464 KB |
testcase_01 | AC | 3 ms
7,468 KB |
testcase_02 | WA | - |
testcase_03 | AC | 3 ms
7,396 KB |
testcase_04 | AC | 3 ms
7,364 KB |
testcase_05 | AC | 2 ms
7,344 KB |
testcase_06 | WA | - |
testcase_07 | AC | 2 ms
7,360 KB |
testcase_08 | AC | 3 ms
7,436 KB |
testcase_09 | AC | 3 ms
7,372 KB |
testcase_10 | AC | 3 ms
7,400 KB |
testcase_11 | WA | - |
testcase_12 | WA | - |
testcase_13 | WA | - |
testcase_14 | WA | - |
testcase_15 | WA | - |
testcase_16 | AC | 2 ms
7,428 KB |
testcase_17 | AC | 3 ms
7,508 KB |
testcase_18 | WA | - |
testcase_19 | AC | 3 ms
7,364 KB |
testcase_20 | AC | 2 ms
7,388 KB |
testcase_21 | AC | 3 ms
7,376 KB |
testcase_22 | AC | 3 ms
7,404 KB |
コンパイルメッセージ
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 #-} import Control.Monad.State import Data.Bits import Data.Bool import Data.Char import Data.Coerce import Data.Word import qualified Data.ByteString as BS import qualified Data.ByteString.Char8 as BSC8 import qualified Data.Vector.Fusion.Stream.Monadic as VFSM import qualified Data.Vector.Unboxed as VU import qualified Data.Vector.Unboxed.Mutable as VUM 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 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 #-} 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 -> (Int -> m ()) -> m () rev l r = flip VFSM.mapM_ (streamR l (r + 1)) {-# INLINE rev #-} main :: IO () main = do n <- readLn :: IO Int w <- seqInput n let s = VU.sum w if odd s then putStrLn "impossible" else do dp <- VUM.replicate (5001) True rep n $ \i -> rev (s `div` 2) (w VU.! i) $ \j -> do dpjwi <- VUM.unsafeRead dp (j - w VU.! i) VUM.unsafeModify dp (\k -> k .|. dpjwi) j putStrLn . bool "impossible" "possible" =<< VUM.unsafeRead dp (s `div` 2)