Submission #40301577

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.Array.ST
import Control.Monad.ST
import Data.Array
main = do
  [n] <- bsGetLnInts
  as <- bsGetLnInts
  bs <- bsGetLnInts
  let ans = abc296f n as bs
  putStrLn $ if ans then "Yes" else "No"
bsGetLnInts :: IO [Int]
bsGetLnInts = unfoldr (BS.readInt . BS.dropWhile isSpace) <$> BS.getLine
abc296f :: Int -> [Int] -> [Int] -> Bool
abc296f n as bs = cond1 && (cond2 || cond3)
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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

import Data.Array.ST
import Control.Monad.ST
import Data.Array

main = do
  [n] <- bsGetLnInts
  as <- bsGetLnInts
  bs <- bsGetLnInts
  let ans = abc296f n as bs
  putStrLn $ if ans then "Yes" else "No"

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

abc296f :: Int -> [Int] -> [Int] -> Bool
abc296f n as bs = cond1 && (cond2 || cond3)
  where
    cA = accumArray (+) 0 (1,n) [(a,1) | a <- as]
    cB = accumArray (+) 0 (1,n) [(b,1) | b <- bs]
    -- 両者の要素が一致
    cond1 = cA == cB
    -- カウントが1でない、つまりどこかに重複があるなら、何とでもなる
    cond2 = any (1 /=) (elems cA)
    -- 値の重複がないとき、反転数の偶奇が両者で等しいことが必要。
    -- <=> P[i] = B[A[i]] が偶置換
    ba = listArray (1,n) bs
    cond3 = runST $ do
      p <- newListArray (1,n) $ map (ba !) as
      loop p 1 True
    loop :: STUArray s Int Int -> Int -> Bool -> ST s Bool
    loop p i ans
      | n < i = return ans
      | otherwise =
      do
        j <- readArray p i
        if i == j then loop p (succ i) ans else do
          pj <- readArray p j
          writeArray p i pj
          writeArray p j j
          loop p i (not ans)

Submission Info

Compile Error

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

Judge Result