結果

問題 No.490 yukiソート
ユーザー atuk721atuk721
提出日時 2017-05-06 15:02:48
言語 Haskell
(9.8.2)
結果
WA  
実行時間 -
コード長 1,058 bytes
コンパイル時間 6,871 ms
コンパイル使用メモリ 199,696 KB
実行使用メモリ 377,312 KB
最終ジャッジ日時 2023-10-12 15:05:19
合計ジャッジ時間 23,313 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 3 ms
7,436 KB
testcase_01 WA -
testcase_02 AC 3 ms
7,408 KB
testcase_03 AC 2 ms
7,372 KB
testcase_04 AC 32 ms
17,588 KB
testcase_05 AC 32 ms
17,748 KB
testcase_06 AC 32 ms
17,536 KB
testcase_07 AC 32 ms
17,688 KB
testcase_08 AC 32 ms
17,536 KB
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 WA -
testcase_22 WA -
testcase_23 WA -
testcase_24 AC 2 ms
7,404 KB
testcase_25 AC 2 ms
7,380 KB
testcase_26 AC 3 ms
7,344 KB
testcase_27 AC 3 ms
7,292 KB
testcase_28 AC 2 ms
7,364 KB
testcase_29 AC 3 ms
7,340 KB
testcase_30 AC 3 ms
7,352 KB
testcase_31 WA -
testcase_32 WA -
testcase_33 WA -
testcase_34 WA -
testcase_35 WA -
権限があれば一括ダウンロードができます
コンパイルメッセージ
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 qualified Control.Monad as M
import qualified Control.Monad.ST as S
import qualified Data.IntMap.Lazy as Map
import qualified Data.Vector.Unboxed as V
import qualified Data.Vector.Unboxed.Mutable as VM

main :: IO ()
main = do
  n <- readLn
  xs <- map read . words <$> getLine
  putStrLn . unwords . map show $ yukisort n xs

yukisort :: Int -> [Int] -> [Int]
yukisort n xs = V.toList $ S.runST $ do
  vec <- VM.unsafeNew n
  mapM_ (\(k, v) -> VM.write vec k v) $ zip [0..] xs
  mapM_ (proc vec) [1..(2 * n - 3)]
  V.freeze vec
    where calcMap = createMap n
          proc vec i = do
            let comb = (Map.!) calcMap i
            M.forM_ comb $ \(p, q) -> do
              a <- VM.unsafeRead vec p
              b <- VM.unsafeRead vec q
              M.when (a > b) $ VM.unsafeSwap vec p q

createMap :: Int -> Map.IntMap [(Int, Int)]
createMap n = foldl (\m (p, q) -> Map.insertWith insertFunc (p + q) [(p, q)] m) Map.empty comb
  where comb = [(p, q) | p <- [0..n - 1], q <- [0..n - 1], p < q]
        insertFunc new old = new !! 0 : old
0