結果
問題 | No.833 かっこいい電車 |
ユーザー | Roki |
提出日時 | 2019-06-23 02:05:29 |
言語 | Haskell (9.8.2) |
結果 |
TLE
|
実行時間 | - |
コード長 | 2,501 bytes |
コンパイル時間 | 9,973 ms |
コンパイル使用メモリ | 185,376 KB |
実行使用メモリ | 58,948 KB |
最終ジャッジ日時 | 2023-09-14 21:08:12 |
合計ジャッジ時間 | 16,731 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge13 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | TLE | - |
testcase_01 | -- | - |
testcase_02 | -- | - |
testcase_03 | -- | - |
testcase_04 | -- | - |
testcase_05 | -- | - |
testcase_06 | -- | - |
testcase_07 | -- | - |
testcase_08 | -- | - |
testcase_09 | -- | - |
testcase_10 | -- | - |
testcase_11 | -- | - |
testcase_12 | -- | - |
testcase_13 | -- | - |
testcase_14 | -- | - |
testcase_15 | -- | - |
testcase_16 | -- | - |
testcase_17 | -- | - |
testcase_18 | -- | - |
testcase_19 | -- | - |
testcase_20 | -- | - |
testcase_21 | -- | - |
testcase_22 | -- | - |
testcase_23 | -- | - |
testcase_24 | -- | - |
testcase_25 | -- | - |
testcase_26 | -- | - |
testcase_27 | -- | - |
testcase_28 | -- | - |
testcase_29 | -- | - |
testcase_30 | -- | - |
testcase_31 | -- | - |
コンパイルメッセージ
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
ソースコード
module Main where import Control.Monad (unless) import Control.Monad.Fix (fix) import Data.List (find, findIndex) import Data.Maybe (isJust) import Data.Array.IArray (Array, listArray, (!)) import qualified Data.Set as S data Vehicle = Vehicle { identifier :: Int, cool :: Int } deriving Show instance Eq Vehicle where (==) (Vehicle i _) (Vehicle j _) = i == j instance Ord Vehicle where compare (Vehicle i _) (Vehicle j _) = compare i j dropAt :: Int -> [a] -> [a] dropAt = f 0 where f i t (x:xs) | i == t = xs | otherwise = x : f (succ i) t xs f _ _ _ = [] memberBy :: Ord a => (a -> Bool) -> S.Set a -> Bool memberBy = (.) isJust . flip (.) S.toList . find lookupBy :: Ord a => (a -> Bool) -> S.Set a -> Maybe a lookupBy = flip (.) S.toList . find findSetIndexVehicle :: Int -> [S.Set Vehicle] -> Maybe Int findSetIndexVehicle i = findIndex (memberBy ((==i) . identifier)) lookupVehicle :: Int -> S.Set Vehicle -> Maybe Vehicle lookupVehicle i = lookupBy ((==i) . identifier) connect :: Int -> [S.Set Vehicle] -> [S.Set Vehicle] connect i vs = flip (maybe vs) (findSetIndexVehicle i vs) $ \xi -> let dx = dropAt xi vs in flip (maybe vs) (findSetIndexVehicle (succ i) dx) $ \yi -> (vs !! xi) `S.union` (dx !! yi) : dropAt yi dx separate :: Int -> [S.Set Vehicle] -> [S.Set Vehicle] separate i vs = flip (maybe vs) (findSetIndexVehicle i vs) $ \xi -> let x = vs !! xi in flip (maybe vs) (lookupVehicle (succ i) x) $ \x1 -> [S.delete x1 x, S.singleton x1] ++ dropAt xi vs remodel :: Int -> [S.Set Vehicle] -> [S.Set Vehicle] remodel i vs = flip (maybe vs) (findSetIndexVehicle i vs) $ \xi -> let x = vs !! xi in flip (maybe vs) (lookupVehicle i x) $ \y -> S.insert (y { cool = succ (cool y) }) x : dropAt xi vs attractiveness :: Int -> [S.Set Vehicle] -> Maybe Int attractiveness i vs = flip (maybe Nothing) (findSetIndexVehicle i vs) $ Just . foldr ((+) . cool) 0 . S.toList . (vs !!) main :: IO () main = let queryMap = listArray (1, 3) [connect, separate, remodel] :: Array Int (Int -> [S.Set Vehicle] -> [S.Set Vehicle]) in do [n, q] <- map (read :: String -> Int) . words <$> getLine as <- zipWith ((.) S.singleton . (flip (.) read . Vehicle)) [1..n] . words <$> getLine ($ (q, as)) . fix $ \f (i, a) -> unless (i == 0) $ do [qy, xi] <- map read . words <$> getLine if qy > 3 then maybe (return ()) ((<*) (f (pred i, a)) . print) (attractiveness xi a) else f (pred i, (queryMap ! qy) xi a)