Submission #2406367

---

Source Code Expand

{-# OPTIONS_GHC -O2 -funbox-strict-fields #-}
import           Control.Monad.ST            (ST, runST)
import           Data.Bits                   (shiftL, shiftR, testBit, (.&.))
import qualified Data.ByteString.Char8       as BC
import           Data.Maybe                  (fromJust)
import qualified Data.Vector.Unboxed         as V
import qualified Data.Vector.Unboxed.Mutable as VM


main :: IO ()
main = do
  n <- readLn
  as <- getInts
  bs <- getInts
  print 0
  print $ solve n as bs

solve :: Int -> [Int] -> [Int] -> Int
solve n as bs = sum $ map kXorBit [0 .. 28] where
  bv = V.fromList bs
  kXorBit k = if odd s then t else 0 where
    t = 1 `shiftL` k
    t2 = 1 `shiftL` (k + 1)
    cs = sort' $ V.map modT2 bv
    s = sum $ map count as
    mask = t2 - 1
    modT2 = (mask .&.)
    count a = (t12 - t01) + (n - t23) where
      t01 = binarySearch cs $ t - a'
      t12 = binarySearch cs $ t2 - a'
      t23 = binarySearch cs $ 3 * t - a'
      a' = modT2 a

binarySearch :: V.Vector Int -> Int -> Int
binarySearch xs y = go 0 $ V.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 `V.unsafeIndex` m

odd' :: Int -> Bool
odd' n = testBit n 0

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

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

sort' :: V.Vector Int -> V.Vector Int
sort' xs = runST $ do
  v <- V.thaw $ xs
  quicksort v 0 $ VM.length v
  V.freeze v

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

quicksort :: VM.STVector s Int -> IndType -> IndType -> ST s ()
quicksort work iStart iEnd
    | iEnd - iStart <= 1 = return ()
    | otherwise =
      do
        pivot <- VM.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 do
                return lower
              else do
                swapWork lower higher
                divide pivot (lower + 1) (higher - 1)

    shrinkLower pivot iS' iE'
        | iS' > iE' = return iS'
        | otherwise =
          do
            x <- VM.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 <- VM.unsafeRead work iE'
            if x <= pivot
              then
                return iE'
              else
                shrinkHigher pivot iS' (iE' - 1)

    swapWork i j = VM.unsafeSwap work i j

Submission Info

Judge Result