結果
| 問題 |
No.45 回転寿司
|
| ユーザー |
 かりあげクン
|
| 提出日時 | 2020-09-05 13:04:28 |
| 言語 | Haskell (9.10.1) |
| 結果 |
CE
(最新)
AC
(最初)
|
| 実行時間 | - |
| コード長 | 11,491 bytes |
| コンパイル時間 | 275 ms |
| コンパイル使用メモリ | 169,588 KB |
| 最終ジャッジ日時 | 2024-11-14 23:49:36 |
| 合計ジャッジ時間 | 671 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge4 |
（要ログイン）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、clay言語の場合は開発者のデバッグのため、公開されます。
ただし、clay言語の場合は開発者のデバッグのため、公開されます。
コンパイルメッセージ
Loaded package environment from /home/judge/.ghc/x86_64-linux-9.8.2/environments/default
Main.hs:25:14: warning: [GHC-53692] [-Wdeprecated-flags]
-XTypeInType is deprecated: use -XDataKinds and -XPolyKinds instead
|
25 | {-# LANGUAGE TypeInType #-}
| ^^^^^^^^^^
[1 of 2] Compiling Main ( Main.hs, Main.o )
Main.hs:63:1: error: [GHC-61948]
Could not find module ‘Data.ByteString.Lazy.Builder’.
Perhaps you meant
Data.ByteString.Builder (from bytestring-0.12.1.0)
Data.ByteString.Lazy.Char8 (from bytestring-0.12.1.0)
Data.ByteString.Lazy.ReadInt
Use -v to see a list of the files searched for.
|
63 | import qualified Data.ByteString.Lazy.Builder as BSLB
| ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
Main.hs:67:1: error: [GHC-87110]
Could not load module ‘Data.Graph’.
It is a member of the hidden package ‘containers-0.6.8’.
Use -v to see a list of the files searched for.
|
67 | import qualified Data.Graph as Graph
| ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
Main.hs:68:1: error: [GHC-87110]
Could not load module ‘Data.IntMap’.
It is a member of the hidden package ‘containers-0.6.8’.
Use -v to see a list of the files searched for.
|
68 | import Data.IntMap (IntMap)
| ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
Main.hs:69:1: error: [GHC-87110]
Could not load module ‘Data.IntMap’.
It is a member of the hidden package ‘containers-0.6.8’.
Use -v to see a list of the files searched for.
|
69 | import qualified Data.IntMap as IntMap
| ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
Main.hs:70:1: error: [GHC-87110]
Could not load module ‘Data.IntSet’.
It is a member of the hidden package ‘containers-0.6.8’.
Use -v to see a list of the files searched fo
ソースコード
{-# LANGUAGE BangPatterns #-}
{-# LANGUAGE BinaryLiterals #-}
{-# LANGUAGE CPP #-}
{-# LANGUAGE DeriveFunctor #-}
{-# LANGUAGE DerivingStrategies #-}
{-# LANGUAGE DerivingVia #-}
{-# LANGUAGE FlexibleContexts #-}
{-# LANGUAGE FlexibleInstances #-}
{-# LANGUAGE GeneralizedNewtypeDeriving #-}
{-# LANGUAGE KindSignatures #-}
{-# LANGUAGE LambdaCase #-}
{-# LANGUAGE MagicHash #-}
{-# LANGUAGE MultiParamTypeClasses #-}
{-# LANGUAGE MultiWayIf #-}
{-# LANGUAGE NumericUnderscores #-}
{-# LANGUAGE OverloadedStrings #-}
{-# LANGUAGE PatternSynonyms #-}
{-# LANGUAGE RankNTypes #-}
{-# LANGUAGE RecordWildCards #-}
{-# LANGUAGE ScopedTypeVariables #-}
{-# LANGUAGE StandaloneDeriving #-}
{-# LANGUAGE TupleSections #-}
{-# LANGUAGE TypeApplications #-}
{-# LANGUAGE TypeFamilies #-}
{-# LANGUAGE TypeInType #-}
{-# LANGUAGE UnboxedTuples #-}
-------------------------------------------------------------------------------
-------------------------------------------------------------------------------
-------------------------------------------------------------------------------
{- base -}
import Control.Applicative
import qualified Control.Arrow as Arrow
import Control.Monad
import Control.Monad.ST
import Data.Bits
import Data.Bool
import qualified Data.Char as Char
import Data.Complex
import qualified Data.Foldable as Foldable
import Data.Function
import qualified Data.List as List
import Data.Maybe
import Data.Monoid
import Data.Ord
import Data.Ratio
import Data.Semigroup
import qualified Data.Word as Word
import Foreign hiding (void)
import GHC.Exts
import Unsafe.Coerce
{- array -}
import qualified Data.Array.IO as ArrIO
import qualified Data.Array.MArray as ArrMA
import qualified Data.Array.ST as ArrST
import qualified Data.Array.Storable as ArrStore
import qualified Data.Array.Unboxed as ArrU
{- bytestring -}
import qualified Data.ByteString as BS
import qualified Data.ByteString.Builder as BSB
import qualified Data.ByteString.Builder.Extra as BSBE
import qualified Data.ByteString.Char8 as BSC8
import qualified Data.ByteString.Lazy as BSL
import qualified Data.ByteString.Lazy.Builder as BSLB
import qualified Data.ByteString.Lazy.Char8 as BSLC8
import qualified Data.ByteString.Unsafe as BSU
{- containers -}
import qualified Data.Graph as Graph
import Data.IntMap (IntMap)
import qualified Data.IntMap as IntMap
import Data.IntSet (IntSet)
import qualified Data.IntSet as IntSet
import qualified Data.Sequence as Seq
import qualified Data.Tree as Tree
{- integer-gmp -}
import GHC.Integer.GMP.Internals
{- time -}
import qualified Data.Time.Calendar as Calender
import qualified Data.Time.Calendar.Easter as CalenderE
import qualified Data.Time.Calendar.Julian as CalenderJ
import qualified Data.Time.Calendar.MonthDay as CalenderM
import qualified Data.Time.Calendar.OrdinalDate as CalenderD
import qualified Data.Time.Calendar.WeekDate as CalenderW
import qualified Data.Time.LocalTime as LocalTime
{- transformers -}
import qualified Control.Monad.Trans.Accum as TAccum
import qualified Control.Monad.Trans.Cont as TCont
import qualified Control.Monad.Trans.Identity as TId
import qualified Control.Monad.Trans.Reader as TReader
import qualified Control.Monad.Trans.State.Lazy as TStateL
import qualified Control.Monad.Trans.State.Strict as TStateS
import qualified Control.Monad.Trans.Writer.CPS as TWriteC
import qualified Control.Monad.Trans.Writer.Lazy as TWriteL
import qualified Control.Monad.Trans.Writer.Strict as TWriteS
{- vector -}
import qualified Data.Vector as V
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.Primitive as VP
import qualified Data.Vector.Primitive.Mutable as VPM
import qualified Data.Vector.Unboxed as VU
import qualified Data.Vector.Unboxed.Mutable as VUM
-------------------------------------------------------------------------------
-------------------------------------------------------------------------------
-------------------------------------------------------------------------------
main :: IO ()
main = do
m <- parse1
v <- parseM m
print $ solver v (m - 1)
solver :: VU.Vector Int -> Int -> Int
solver xs = dyna phi psi
where
psi 0 = NELF (xs VU.! 0) Nothing
psi i = NELF (xs VU.! i) (Just (i - 1))
phi (NELF j Nothing) = j
phi (NELF j (Just t)) = max f1 f2
where
f1 = extract t
f2 = case sub t of
NELF _ Nothing -> j
NELF _ (Just t') -> extract t' + j
-------------------------------------------------------------------------------
-------------------------------------------------------------------------------
-------------------------------------------------------------------------------
type Parser a = BSC8.ByteString -> Maybe (a, BSC8.ByteString)
parseInt :: Parser Int
parseInt = fmap (Arrow.second BSC8.tail) . BSC8.readInt
parseChar :: [Char] -> VU.Vector Char
parseChar = VU.fromList
parse1 :: IO Int
parse1 = readLn
parse2 :: IO (Int, Int)
parse2 = (\vec -> (vec VU.! 0, vec VU.! 1)) . VU.unfoldrN 2 parseInt <$> BSC8.getLine
parse3 :: IO (Int, Int, Int)
parse3 = (\vec -> (vec VU.! 0, vec VU.! 1, vec VU.! 2)) . VU.unfoldrN 3 parseInt <$> BSC8.getLine
parse4 :: IO (Int, Int, Int, Int)
parse4 = (\vec -> (vec VU.! 0, vec VU.! 1, vec VU.! 2, vec VU.! 3)) . VU.unfoldrN 4 parseInt <$> BSC8.getLine
parseM :: Int -> IO (VU.Vector Int)
parseM m = VU.unfoldrN m parseInt <$> BSC8.getLine
parseN :: Int -> IO (VU.Vector Int)
parseN n = VU.replicateM n parse1
parseNM :: Int -> Int -> IO (V.Vector (VU.Vector Int))
parseNM n m = V.replicateM n $ VU.unfoldrN m parseInt <$> BSC8.getLine
parseANBN :: Int -> IO (VU.Vector Int, VU.Vector Int)
parseANBN n = do
vectup <- VU.replicateM n $ (\vec -> (vec VU.! 0, vec VU.! 1)) . VU.unfoldr (BSC8.readInt . BSC8.dropWhile Char.isSpace) <$> BSC8.getLine
return $ VU.unzip vectup
parseANBNCN :: Int -> IO (VU.Vector Int, VU.Vector Int, VU.Vector Int)
parseANBNCN n = do
vectup <- VU.replicateM n $ (\vec -> (vec VU.! 0, vec VU.! 1, vec VU.! 2)) . VU.unfoldr (BSC8.readInt . BSC8.dropWhile Char.isSpace) <$> BSC8.getLine
return $ VU.unzip3 vectup
-------------------------------------------------------------------------------
data NELF a = NELF Int (Maybe a)
deriving (Functor)
newtype Fix f = InF { outF :: f (Fix f) }
pair :: (a -> b, a -> c) -> a -> (b, c)
pair (f, g) x = (f x, g x)
cata :: Functor f => (f a -> a) -> (Fix f -> a)
cata phi = phi . fmap (cata phi) . outF
ana :: Functor f => (a -> f a) -> (a -> Fix f)
ana psi = InF . fmap (ana psi) . psi
hylo :: Functor f => (f a -> a) -> (b -> f b) -> (b -> a)
hylo phi psi = phi . fmap (hylo phi psi) . psi -- cata phi . ana psi
meta :: (Functor f, Functor g) => (f a -> a) -> (a -> b) -> (b -> g b) -> (Fix f -> Fix g)
meta phi chi psi = ana psi . chi . cata phi
prepro :: Functor f => (forall a. f a -> f a) -> (f a -> a) -> (Fix f -> a)
prepro chi phi = phi . fmap (prepro chi phi . cata (InF . chi)) . outF
postpro :: Functor f => (forall a. f a -> f a) -> (a -> f a) -> (a -> Fix f)
postpro chi psi = InF . fmap (ana (chi . outF) . postpro chi psi) . psi
para :: Functor f => (f (Fix f, a) -> a) -> (Fix f -> a)
para phi = phi . fmap ((,) <*> para phi) . outF
apo :: Functor f => (a -> f (Either (Fix f) a)) -> (a -> Fix f)
apo psi = InF . fmap (uncurry either (id, apo psi)) . psi
zygo :: Functor f => (f b -> b) -> (f (b, a) -> a) -> (Fix f -> a)
zygo phi phi' = snd . cata (pair (phi . fmap fst, phi'))
cozygo :: Functor f => (a -> f a) -> (b -> f (Either a b)) -> (b -> Fix f)
cozygo psi psi' = ana (uncurry either (fmap Left . psi, psi')) . Right
mutu :: Functor f => (a -> b) -> (f a -> a) -> (Fix f -> b)
mutu chi phi = chi . cata phi
comutu :: Functor f => (b -> a) -> (a -> f a) -> (b -> Fix f)
comutu chi psi = ana psi . chi
data Fx f a x = Fx { unFx :: Either a (f x) }
data Hx f a x = Hx { unHx :: (a, f x) }
instance Functor f => Functor (Fx f a) where
fmap f (Fx (Left x)) = Fx (Left x)
fmap f (Fx (Right x)) = Fx (Right (fmap f x))
instance Functor f => Functor (Hx f a) where
fmap f (Hx (x, y)) = Hx (x, fmap f y)
newtype Free f a = Free { unFree :: Fix (Fx f a) }
newtype CoFree f a = CoFree { unCoFree :: Fix (Hx f a) }
instance Functor f => Functor (Free f) where
fmap f = Free . cata (InF . phi) . unFree
where
phi (Fx (Left a)) = Fx (Left (f a))
phi (Fx (Right b)) = Fx (Right b)
instance Functor f => Functor (CoFree f) where
fmap f = CoFree . ana (psi . outF) . unCoFree
where
psi (Hx (a, x)) = Hx (f a, x)
extract :: Functor f => CoFree f t -> t
extract cf = case outF (unCoFree cf) of
Hx (a, _) -> a
sub :: Functor f => CoFree f a -> f (CoFree f a)
sub cf = case outF (unCoFree cf) of
Hx (_, b) -> fmap CoFree b
inject :: Functor f => a -> Free f a
inject = Free . InF . Fx . Left
histo :: Functor f => (f (CoFree f t) -> t) -> (Fix f -> t)
histo phi = extract . cata (CoFree . InF . fmap unCoFree . Hx . pair (phi, id))
futu :: Functor f => (t -> f (Free f t)) -> (t -> Fix f)
futu psi = ana (uncurry either (psi, id) . unFx . fmap Free . outF . unFree) . inject
chrono :: Functor f => (f (CoFree f b) -> b) -> (a -> f (Free f a)) -> (a -> b)
chrono phi psi = extract . hylo phi' psi' . inject
where
phi' = CoFree . InF . fmap unCoFree . Hx . pair (phi, id)
psi' = uncurry either (psi, id) . unFx . fmap Free . outF . unFree
cochrono :: Functor f => (f (CoFree f t) -> t) -> (t -> f (Free f t)) -> (Fix f -> Fix f)
cochrono phi psi = futu psi . histo phi
dyna :: Functor f => (f (CoFree f b) -> b) -> (a -> f a) -> (a -> b)
dyna phi psi = chrono phi (fmap inject . psi)
codyna :: Functor f => (f b -> b) -> (a -> f (Free f a)) -> (a -> b)
codyna phi psi = cata phi . futu psi
exo :: Functor h => (m b -> b, b -> n b) -> (h b -> m b) -> (h a -> h (g a)) -> (f a -> a, g a -> h a) -> (g a -> b)
exo c f g d = hylo (fst c . f) (g . snd d)
mcata :: (forall b. (b -> a) -> f b -> a) -> (Fix f -> a)
mcata phi = phi (mcata phi) . outF
mana :: (forall b. (a -> b) -> a -> f b) -> (a -> Fix f)
mana psi = InF . psi (mana psi)
mhisto :: (forall b. (b -> a) -> (b -> f b) -> f b -> a) -> (Fix f -> a)
mhisto psi = psi (mhisto psi) outF . outF
-------------------------------------------------------------------------------
-------------------------------------------------------------------------------