Submission #43269537

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import Control.Monad
import qualified Data.ByteString.Char8 as BS
import Data.Char
import Data.List
import Data.Bits
import qualified Data.IntMap as IM
main = do
  [q] <- bsGetLnInts
  foldM_ (\st _ -> do
    qi <- bsGetLnInts
    case qi of
      (1:x:_) -> return $ mode1 st x
      (2:x:_) -> return $ mode2 st x
      (3:_)   -> print (mode3 st) >> return st
    ) (IM.empty, IM.empty) [1..q]
bsGetLnInts :: IO [Int]
bsGetLnInts = BS.getLine >>= return . unfoldr (BS.readInt . BS.dropWhile isSpace)
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

import Control.Monad
import qualified Data.ByteString.Char8 as BS
import Data.Char
import Data.List

import Data.Bits
import qualified Data.IntMap as IM

main = do
  [q] <- bsGetLnInts
  foldM_ (\st _ -> do
    qi <- bsGetLnInts
    case qi of
      (1:x:_) -> return $ mode1 st x
      (2:x:_) -> return $ mode2 st x
      (3:_)   -> print (mode3 st) >> return st
    ) (IM.empty, IM.empty) [1..q]

bsGetLnInts :: IO [Int]
bsGetLnInts = BS.getLine >>= return . unfoldr (BS.readInt . BS.dropWhile isSpace)

type State =
  ( IM.IntMap Int -- 黒板の数のmultiset
  , IM.IntMap Int -- XORの値のmultiset
  )

mode1 (xm, am) x =
  case IM.lookup x xm of
    Just k  -> output1 0
    Nothing ->
      case (IM.lookupLT x xm, IM.lookupGT x xm) of
        (Nothing, Nothing) -> output0
        (Just (x0,_), Nothing) -> output1 (xor x0 x)
        (Nothing, Just (x2,_)) -> output1 (xor x2 x)
        (Just (x0,_), Just (x2,_)) -> output3 (xor x0 x2) (xor x0 x) (xor x2 x)
  where
    output am = (insertMS x xm, am)
    output0   = output am
    output1 a = output $ insertMS a am
    output3 a1 a2 a3 = output $ insertMS a3 $ insertMS a2 $ deleteMS a1 am

mode2 (xm, am) x =
  case IM.lookup x xm of
    Just k | k > 1 -> output1 0
    Just 1 ->
      case (IM.lookupLT x xm, IM.lookupGT x xm) of
        (Nothing, Nothing) -> output0
        (Just (x0,_), Nothing) -> output1 (xor x0 x)
        (Nothing, Just (x2,_)) -> output1 (xor x2 x)
        (Just (x0,_), Just (x2,_)) -> output3 (xor x0 x2) (xor x0 x) (xor x2 x)
  where
    output am = (deleteMS x xm, am)
    output0 = output am
    output1 a = output $ deleteMS a am
    output3 a1 a2 a3 = output $ insertMS a1 $ deleteMS a2 $ deleteMS a3 am

mode3 st@(_, am) = fst $ IM.findMin am

insertMS x ms = IM.insertWith (+) x 1 ms
deleteMS x ms = IM.update dec x ms
  where
    dec 1 = Nothing
    dec k = Just (pred k)

-- 公式解説のとおり
-- 不要な部分を削った

Submission Info

Compile Error

Loaded package environment from /home/contestant/.ghc/x86_64-linux-8.8.3/environments/default

Judge Result