Submission #993346
Source Code Expand
{-# LANGUAGE ScopedTypeVariables #-} import Control.Applicative import Control.Monad import Control.Monad.State import Control.DeepSeq import Data.Array import Data.Bits import Data.Char import Data.Functor.Identity import Data.List import Data.Maybe import Data.Ord import Data.Tree import Data.Tuple import qualified System.IO import qualified Data.Map as M import qualified Data.Set as S import qualified Data.Sequence as Q import qualified Data.ByteString.Char8 as B main = do (n,m) <-getIntPair xss <- group . sort <$> getInts let as = accumArray (+) 0 (0,m-1) [(head ys`mod`m, length ys`div`2) | ys <- xss] let bs = accumArray (+) 0 (0,m-1) [(head ys`mod`m, length ys`mod`2) | ys <- xss] -- print as -- print bs print $ sum [f (i==j) (as!i) (as!j) (bs!i) (bs!j) | i <- [0..m`div`2], let j = (-i)`mod`m] f True a _ b _ = a + (b`div`2) f False a0 a1 b0 b1 | b0 >= b1 = a0+a1+b1+ min ((b0-b1)`div`2) a1 | otherwise = a0+a1+b0+ min ((b1-b0)`div`2) a0 type Z = Int type Q = Rational type R = Double type S = String fint :: (Integral a, Num b) => a -> b fint = fromIntegral getInt = fst . fromJust . B.readInt <$> B.getLine getIntPair = (\[a,b]->(a,b)) <$> getInts getInts = map (fst . fromJust . B.readInt) . B.words <$> B.getLine getStr = B.unpack <$> B.getLine yesNo :: Bool -> String yesNo True = "Yes" yesNo False = "No" printList :: (Show a) => [a] -> IO () printList = putStrLn . unwords . map show readLnList :: (Read a) => IO [a] readLnList = map read . words <$> getLine ----- Union-find type UnionFindT v m a = StateT (M.Map v (UnionFindVal v)) m a newtype UnionFindVal v = UnionFindVal v runUnionFindT :: (Monad m) => UnionFindT v m a -> m a runUnionFindT = flip evalStateT $ M.empty runUnionFind = runIdentity . runUnionFindT ufFresh :: (Monad m, Ord v) => v -> UnionFindT v m () ufFresh v = modify $ M.insert v (UnionFindVal v) ufClass :: (Monad m, Ord v) => v -> UnionFindT v m v ufClass v = do (UnionFindVal pv) <- gets (M.! v) if v == pv then return v else do c <- ufClass pv modify $ M.insert v (UnionFindVal c) return c ufUnify v w = do cv <- ufClass v cw <- ufClass w modify $ M.insert cw (UnionFindVal cv) return $ cv /= cw
Submission Info
Submission Time | |
---|---|
Task | D - Pair Cards |
User | tos |
Language | Haskell (GHC 7.10.3) |
Score | 700 |
Code Size | 2305 Byte |
Status | AC |
Exec Time | 343 ms |
Memory | 32124 KB |
Judge Result
Set Name | sample | all | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 700 / 700 | ||||
Status |
|
|
Set Name | Test Cases |
---|---|
sample | sample-01.txt, sample-02.txt |
all | sample-01.txt, sample-02.txt, 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt, 01-11.txt, 01-12.txt, 01-13.txt, 01-14.txt, 01-15.txt, 01-16.txt, 01-17.txt, 01-18.txt, 01-19.txt, 01-20.txt, 01-21.txt, 01-22.txt, 01-23.txt, 01-24.txt, 01-25.txt, 01-26.txt, 01-27.txt, 01-28.txt, 01-29.txt, 01-30.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
01-01.txt | AC | 3 ms | 380 KB |
01-02.txt | AC | 306 ms | 24956 KB |
01-03.txt | AC | 308 ms | 23932 KB |
01-04.txt | AC | 314 ms | 23932 KB |
01-05.txt | AC | 304 ms | 23932 KB |
01-06.txt | AC | 307 ms | 24956 KB |
01-07.txt | AC | 291 ms | 23932 KB |
01-08.txt | AC | 305 ms | 24060 KB |
01-09.txt | AC | 305 ms | 23036 KB |
01-10.txt | AC | 313 ms | 24444 KB |
01-11.txt | AC | 311 ms | 24956 KB |
01-12.txt | AC | 60 ms | 14076 KB |
01-13.txt | AC | 53 ms | 14332 KB |
01-14.txt | AC | 330 ms | 32124 KB |
01-15.txt | AC | 339 ms | 31100 KB |
01-16.txt | AC | 343 ms | 31100 KB |
01-17.txt | AC | 338 ms | 30332 KB |
01-18.txt | AC | 317 ms | 29052 KB |
01-19.txt | AC | 336 ms | 29052 KB |
01-20.txt | AC | 320 ms | 31100 KB |
01-21.txt | AC | 240 ms | 16764 KB |
01-22.txt | AC | 245 ms | 17788 KB |
01-23.txt | AC | 261 ms | 16764 KB |
01-24.txt | AC | 259 ms | 16764 KB |
01-25.txt | AC | 247 ms | 16764 KB |
01-26.txt | AC | 262 ms | 17788 KB |
01-27.txt | AC | 144 ms | 16764 KB |
01-28.txt | AC | 14 ms | 3068 KB |
01-29.txt | AC | 6 ms | 1660 KB |
01-30.txt | AC | 8 ms | 2044 KB |
sample-01.txt | AC | 3 ms | 380 KB |
sample-02.txt | AC | 3 ms | 380 KB |