結果

問題 No.429 CupShuffle
ユーザー aimyaimy
提出日時 2017-06-21 09:58:45
言語 Haskell
(9.6.2)
結果
AC  
実行時間 695 ms / 2,000 ms
コード長 896 bytes
コンパイル時間 5,987 ms
コンパイル使用メモリ 164,060 KB
実行使用メモリ 101,144 KB
最終ジャッジ日時 2023-07-25 15:10:58
合計ジャッジ時間 8,607 ms
ジャッジサーバーID
(参考情報)
judge15 / judge12
このコードへのチャレンジ(β)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 5 ms
9,780 KB
testcase_01 AC 3 ms
7,832 KB
testcase_02 AC 3 ms
7,804 KB
testcase_03 AC 3 ms
7,876 KB
testcase_04 AC 5 ms
9,396 KB
testcase_05 AC 3 ms
7,680 KB
testcase_06 AC 5 ms
9,816 KB
testcase_07 AC 5 ms
9,828 KB
testcase_08 AC 3 ms
8,236 KB
testcase_09 AC 5 ms
9,584 KB
testcase_10 AC 53 ms
18,556 KB
testcase_11 AC 695 ms
101,144 KB
testcase_12 AC 515 ms
93,952 KB
testcase_13 AC 655 ms
93,108 KB
testcase_14 AC 675 ms
91,316 KB
testcase_15 AC 3 ms
7,540 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
Loaded package environment from /home/judge/.ghc/x86_64-linux-9.6.1/environments/default
[1 of 2] Compiling Main             ( Main.hs, Main.o )
[2 of 2] Linking a.out

ソースコード

diff #

import Data.IntMap.Strict ((!))
import qualified Data.IntMap.Strict as M
import qualified Data.ByteString.Char8 as B
import Data.List
import Data.Maybe
import Control.Monad

readInt = fst . fromJust . B.readInt
swap i j im = M.insert j (im!i) (M.insert i (im!j) im)

main = do
 [n,k,x] <- map read . words <$> getLine
 ab1s <- map (map readInt . B.words) <$> replicateM (x-1) B.getLine
 getLine
 ab2s <- map (map readInt . B.words) <$> replicateM (k-x) B.getLine
 cs <- map read . words <$> getLine
 let start = M.fromDistinctAscList (zip [1..n] [1..n])
 let goal = M.fromDistinctAscList (zip [1..n] cs)
 putStrLn $ unwords $ map show (shuffle start ab1s goal ab2s)

shuffle start ab1s goal ab2s = map succ $ findIndices id (zipWith (/=) prev next)
 where
  prev = M.elems $ foldl' (\acc [a,b] -> swap a b acc) start ab1s
  next = M.elems $ foldl' (\acc [a,b] -> swap a b acc) goal (reverse ab2s)
0