Submission #2413135

---

Source Code Expand

{-# OPTIONS_GHC -O2 -funbox-strict-fields #-}
module Main
where

import           Control.Applicative
import           Control.Monad
import           Control.Monad.ST
import           Data.Array
import           Data.Bits
import qualified Data.ByteString.Char8       as BC
import           Data.List
import           Data.Maybe
import           Data.STRef
import qualified Data.Vector                 as VU
import qualified Data.Vector.Mutable         as VUM
--import qualified Data.Vector.Unboxed         as VU
--import qualified Data.Vector.Unboxed.Mutable as VUM

--{-# INLINE bucketsort #-}
--bucketsort :: (Int, Int) -> [Int] -> [Int]
--bucketsort = bucketsortBy id

--{-# INLINE bucketsortBy #-}
--bucketsortBy :: (a -> Int) -> (Int, Int) -> [a] -> [a]
--bucketsortBy getkey dom = concatMap reverse . filter (not . null)
--    . elems . accumArray (flip (:)) [] dom . map (\x -> (getkey x, x))

--{-# INLINE bucketsortDescBy #-}
--bucketsortDescBy :: (a -> Int) -> (Int, Int) -> [a] -> [a]
--bucketsortDescBy getkey dom = reverse . concat . filter (not . null)
--    . elems . accumArray (flip (:)) [] dom . map (\x -> (getkey x, x))

--marge :: Ord a => VM.STVector s a -> VM.STVector s a -> VM.STVector s a -> ST s ()
--marge u v ret
--  | VM.null u = VM.copy ret v
--  | VM.null v = VM.copy ret u
--  | otherwise = do
--        x <- VM.read u 0
--        y <- VM.read v 0
--        if x > y then marge v u ret else do
--            VM.write ret 0 x
--            marge (VM.tail u) v (VM.tail ret)

--testMarge :: V.Vector Int
--testMarge = runST $ do
--    x <- V.thaw $ V.fromList ([1, 4] :: [Int])
--    y <- V.thaw $ V.fromList ([2, 3] :: [Int])
--    res <- VM.new 4
--    marge x y res
--    V.freeze res

--msort :: Ord a => V.Vector a -> V.Vector a
--msort v = runST $ do
--    v' <- V.thaw v
--    work <- VM.new $ VM.length v'
--    msort_ v' work
--    V.unsafeFreeze v'

--msort_ :: Ord a => VM.STVector s a -> VM.STVector s a -> ST s ()
--msort_ v work
--  | VM.length v <= 1 = return ()
--  | otherwise        = do
--        VM.copy lwork lv
--        VM.copy rwork rv
--        msort_ lwork lv
--        msort_ rwork rv
--        marge lwork rwork v
--        where
--            toHalf vm = VM.splitAt (VM.length vm `div` 2) vm
--            (lv, rv) = toHalf v
--            (lwork, rwork) = toHalf work


main :: IO ()
main = do
    n <- readLn :: IO Int
    as <- getInts
    bs <- getInts
    print $ sum $ eachFigure' as bs <$> [0..28]

readInts :: BC.ByteString -> [Int]
readInts = map (fst . fromJust . BC.readInt) . BC.words

getInts :: IO [Int]
getInts = readInts <$> BC.getLine

upperBoundImpl :: Int -> (Int, Int) -> VU.Vector Int -> Int
upperBoundImpl key (l, r) f =
    let mid = (l + r) `unsafeShiftR` 1
    in  if r - l <= 1 then r else
        if f `VU.unsafeIndex` mid <= key
            then upperBoundImpl key (mid, r) f
            else upperBoundImpl key (l, mid) f

--binarySearch :: VU.Vector Int -> Int -> Int
--binarySearch xs y = go 0 $ VU.length xs where
--    go l r
--        | l == r = l
--        | x < y = go (m + 1) r
--        | x >= y = go l m
--        where m = (r + l) `shiftR` 1
--              x = xs `VU.unsafeIndex` m

upperBound :: Int -> (Int, Int) -> VU.Vector Int -> Int
upperBound key (l, r) = upperBoundImpl key (l - 1, r)

--test :: IO()
--test = undefined

unsafeBit = (1 `unsafeShiftL`)

xorOnFigure :: VU.Vector Int -> Int -> Int -> Int
xorOnFigure sorted k a =
    let n = VU.length sorted
        notCarriers = upperBound (unsafeBit (k + 1) - 1 - a) (0, n) sorted
        i = upperBound (unsafeBit k - 1 - a) (0, n) sorted
        j = upperBound (unsafeBit k * 3 - 1 - a) (0, n) sorted
    in  (notCarriers - i) + (n - j)

--eachFigure :: Int -> [Int] -> [Int] -> Int
--eachFigure k as sortedBs =
--    let v = VU.fromList $ (.&. (unsafeBit (k + 1) - 1)) <$> sortedBs
--    in  foldr1 xor $ map (xorOnFigure v k) $ (.&. (unsafeBit (k + 1) - 1)) <$> as

eachFigure' :: [Int] -> [Int] -> Int -> Int
eachFigure' as bs k =
    let v = sort' $ VU.map (.&. (unsafeBit (k + 1) - 1)) $ VU.fromList bs
    in  if odd $ sum $ map (xorOnFigure v k) $ (.&. (unsafeBit (k + 1) - 1)) <$> as
        then unsafeBit k
        else 0

--build :: Int -> [Int] -> [[Int]]
--build 29 _ = []
--build k bs = sorted : build (k + 1) sorted
--    where sorted = bucketsortBy (\w -> if testBit w k then 1 else 0) (0, 1) bs :: [Int]

sort' :: VU.Vector Int -> VU.Vector Int
sort' = VU.modify (\v -> quicksort v 0 (VUM.length v))

-- https://github.com/as-capabl/haskell-qsort-pfm/blob/master/src/UV.hs
type IndType = Int

quicksort :: VUM.STVector s Int -> IndType -> IndType -> ST s ()
quicksort work iStart iEnd
    | iEnd - iStart <= 1 = return ()
    | otherwise =
        do
        pivot <- VUM.unsafeRead work ((iEnd + iStart) `shiftR` 1)
        med <- divide pivot iStart (iEnd - 1)
        quicksort work iStart med
        quicksort work med iEnd
    where
    divide pivot iS' iE'
        | iS' > iE' = return iS'
        | otherwise =
            do
            lower <- shrinkLower pivot iS' iE'
            higher <- shrinkHigher pivot lower iE'
            if lower >= higher
                then return lower
                else do
                swapWork lower higher
                divide pivot (lower + 1) (higher - 1)

    shrinkLower pivot iS' iE'
        | iS' > iE' = return iS'
        | otherwise =
            do
            x <- VUM.unsafeRead work iS'
            if x >= pivot
                then
                return iS'
                else
                shrinkLower pivot (iS' + 1) iE'

    shrinkHigher pivot iS' iE'
        | iS' > iE' = return iE'
        | otherwise =
            do
            x <- VUM.unsafeRead work iE'
            if x <= pivot
                then
                return iE'
                else
                shrinkHigher pivot iS' (iE' - 1)

    swapWork = VUM.unsafeSwap work

Submission Info

Judge Result