Beautiful Pairs

  • + 0 comments

    Haskell

    The mandatory "must change a value" was kind of bullshit, but otherwise...

    module Main where
    
    import qualified Data.Map  as M
    import qualified Data.Set  as S
    
    dist :: [Int] -> M.Map Int Int
    dist xs = M.fromListWith (+) [(x, 1) | x <- xs]
    
    solve :: [Int] -> [Int] -> Int
    solve as bs = do
        let sab = S.fromList $ as ++ bs
        let mbase = M.fromList [(x, 0) | x <- S.elems sab]
        let ma = M.unionWith (+) mbase $ dist as
        let mb = M.unionWith (+) mbase $ dist bs
        let naturals = sum $ M.unionWith min ma mb
        let deltas = M.unionWith (-) mb ma
        let nonzeros = M.filter (/= 0) deltas
        let (poss, negs) = M.partition (> 0) nonzeros
        let correction = if null poss || null negs then -1 else 1
        naturals + correction
    
    main :: IO ()
    main = do
        _ <- getLine
        as <- map read . words <$> getLine :: IO [Int]
        bs <- map read . words <$> getLine :: IO [Int]
        print $ solve as bs