글 읽기 - 시간 초과 / 이상한 컴파일 에러

haskell_brooks_curry 6년 전 0

제일 최근에 제출한 8138060번 소스코드(아래 첨부)를 로컬에서 실행했을 때 / 코드포스에서 테스트해보았을 때 최악의 경우 각각 0.6~0.7초 만에 통과가 되는데 백준에서는 계속 시간초과가 납니다. 혹시 수행 시간이 실제로 어느 정도로 측정되는지 확인 부탁드릴 수 있을까요?

또, 이 문제 뿐만 아니라 haskell 제출시 가끔 발생하는 현상인데 8138052번과 8138060번이 소스코드가 완전히 똑같음에도 불구하고 하나는 컴파일 에러가 발생합니다(아무런 에러 메시지도 나오지 않습니다)

{-# LANGUAGE DeriveGeneric #-}
import Control.Monad
import Control.Applicative
import Control.DeepSeq
import Control.Exception (evaluate)
import GHC.Generics(Generic)
import Data.Int
import Data.Char
import Data.List
import Data.Maybe
import Data.Function (fix, on)
import Data.Array.Unboxed
import qualified Data.IntMap as IM
import qualified Data.Map as M
import qualified Data.ByteString as BS
import qualified Data.ByteString.Char8 as BS8

data UTuple = UTuple { ufst :: {-# UNPACK #-} !Int
                     , usnd :: {-# UNPACK #-} !Int } deriving (Eq, Ord, Generic)
 
instance NFData UTuple

construct str
    | BS.null str = []
    | isSpace (BS8.head str) = construct (BS8.tail str)
    | otherwise = let Just (i, other) = BS8.readInt str in i : construct other

getInts :: IO [Int]
getInts = construct <$> BS.getLine

mapSort :: [UTuple] -> [UTuple]
mapSort arr = IM.foldrWithKey' (\k a b -> zipWith UTuple (repeat k) a ++ b) [] m
    where m = foldl' (\nm x -> IM.insertWith (++) (ufst x) [usnd x] nm) IM.empty arr

solve :: [UTuple] -> Int64
solve sorted
    | ufst (head sorted) /= usnd (head sorted) = 0
    | length sorted >= 2 && ufst (head sorted) == ufst (sorted !! 1) = 0
    | otherwise = go (groupBy ((==) `on` ufst) $ tail sorted) $ IM.singleton (usnd (head sorted)) 1

m !. k = IM.findWithDefault 0 k m

op :: Int64 -> Int64 -> Int64
op a b = (a* b) `mod` 1000000007

go :: [[UTuple]] -> IM.IntMap Int -> Int64
go [] _ = 1
go (x:xs) m = foldl' (\acc (UTuple a b) -> (fromIntegral $ m !. (b-a)) `op` acc) 1 x `op` go xs m'
    where m' = foldl' (\nm (UTuple _ k) -> IM.insertWith (+) k 1 nm) m x

uzip :: [Int] -> [Int] -> [UTuple]
uzip [] [] = []
uzip (x:xs) (y:ys) = UTuple x y : uzip xs ys

main = do
    [_,s,k] <- BS8.lines <$> BS.getContents
    let sorted = mapSort $ uzip (construct s) (construct k)
    evaluate (rnf sorted)
    print $ solve sorted

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

시간 초과 / 이상한 컴파일 에러

haskell_brooks_curry 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말