結果

問題 No.490 yukiソート
コンテスト
ユーザー atuk721
提出日時 2017-05-06 15:04:57
言語 Haskell
(9.10.1)
結果
CE  
(最新)
AC  
(最初)
実行時間 -
コード長 1,058 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 251 ms
コンパイル使用メモリ 149,760 KB
最終ジャッジ日時 2024-11-15 04:45:30
合計ジャッジ時間 1,010 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、clay言語の場合は開発者のデバッグのため、公開されます。

コンパイルメッセージ
Loaded package environment from /home/judge/.ghc/x86_64-linux-9.8.2/environments/default
[1 of 2] Compiling Main             ( Main.hs, Main.o )

Main.hs:3:1: error: [GHC-87110]
    Could not load module ‘Data.IntMap.Lazy’.
    It is a member of the hidden package ‘containers-0.6.8’.
    Use -v to see a list of the files searched for.
  |
3 | import qualified Data.IntMap.Lazy as Map
  | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

ソースコード

diff #
raw source code 

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 - 4)]
  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