Submission #1990860


Source Code Expand

import qualified Data.ByteString.Char8 as BC
import Data.Maybe (fromJust)
import Data.Array.IO
import Data.List
import Data.Bits
import Control.Monad

type Arr = IOUArray Int Int
type Arr2D = IOUArray (Int, Int) Int

maxLog = 31

main = do
  [n,m,d] <- map read . words <$> getLine :: IO [Int]
  a <- getIntListBC
  pos <- newListArray (1, n) [1..n] :: IO Arr
  foldM amida pos a
  a'' <- getElems pos
  let l = snd . unzip . sort $ zip a'' [1..n]
  table <- newArray ((1, 0), (n, maxLog-1)) 0 :: IO Arr2D
  initTable table l 1
  foldM (makeTable table n) pos [0..maxLog-2]
  ans <- newListArray (1, n) [1..n] :: IO Arr
  foldM (solve table n d) ans [0..maxLog-1]
  ans' <- getElems ans
  let l' = snd . unzip . sort $ zip ans' [1..n]
  putStr $ unlines . map show $ l'

solve :: Arr2D -> Int -> Int -> Arr -> Int -> IO Arr
solve table n i ans k = do
  if shiftR i k .&. 1 == 1
    then do
      ls <- getElems ans
      l <- getLot table k n 1
      update ans l ls
      return ans
    else return ans

update :: Arr -> [Int] -> [Int] -> IO ()
update _   []     []     = return ()
update pos (l:ls) (a:as) = do
  writeArray pos l a
  update pos ls as

initTable :: Arr2D -> [Int] -> Int -> IO ()
initTable table []     _ = return ()
initTable table (i:is) n = do
  writeArray table (n, 0) i
  initTable table is $ n+1

makeTable :: Arr2D -> Int -> Arr -> Int -> IO Arr
makeTable table n pos k = do
  pos' <- getElems pos
  l <- getLot table k n 1
  move pos l pos'
  p <- getElems pos
  let p' = snd . unzip . sort $ zip p [1..n]
  add p' 1
  return pos
  where move :: Arr -> [Int] -> [Int] -> IO ()
        move p []     []     = return ()
        move p (l:ls) (i:is) = do
          writeArray p l i
          move p ls is
        add :: [Int] -> Int -> IO ()
        add []     _ = return ()
        add (p:ps) i = do
          writeArray table (i, k+1) p
          add ps $ i+1

getLot :: Arr2D -> Int -> Int -> Int -> IO [Int]
getLot table k n i
  | n < i = return []
  | otherwise = do
    x <- readArray table (i, k)
    xs <- getLot table k n $ i+1
    return $ x : xs

amida :: Arr -> Int -> IO Arr
amida arr i = do
  x <- readArray arr i
  y <- readArray arr $ i+1
  writeArray arr i y
  writeArray arr (i+1) x
  return arr

bsToInt :: BC.ByteString -> Int
bsToInt = fst . fromJust . BC.readInt

getIntListBC :: IO [Int]
getIntListBC = map bsToInt . BC.words <$> BC.getLine

Submission Info

Submission Time
Task D - 阿弥陀
User amanuko
Language Haskell (GHC 7.10.3)
Score 100
Code Size 2478 Byte
Status AC
Exec Time 3439 ms
Memory 86652 KB

Judge Result

Set Name Subtask1 Subtask2 Subtask3 Subtask4
Score / Max Score 10 / 10 20 / 20 20 / 20 50 / 50
Status
AC × 9
AC × 18
AC × 18
AC × 29
Set Name Test Cases
Subtask1 sample_1.txt, 01_i.txt, 01_random01.txt, 01_random02.txt, 01_random03.txt, 01_random04.txt, 01_random05.txt, 01_random06.txt, 01_random07.txt
Subtask2 sample_1.txt, sample_2.txt, sample_3.txt, 02_i.txt, 02_p.txt, 02_random01.txt, 02_random02.txt, 02_random03.txt, 02_random04.txt, 02_random05.txt, 02_random06.txt, 02_random07.txt, 02_random08.txt, 02_rp01.txt, 02_rp02.txt, 02_rp03.txt, 02_rp04.txt, 02_rp05.txt
Subtask3 sample_1.txt, sample_2.txt, 03_i.txt, 03_random01.txt, 03_random02.txt, 03_random03.txt, 03_random04.txt, 03_random05.txt, 03_random06.txt, 03_random07.txt, 03_random08.txt, 03_random09.txt, 03_random10.txt, 03_random11.txt, 03_random12.txt, 03_random13.txt, 03_random14.txt, 03_random15.txt
Subtask4 sample_1.txt, sample_2.txt, sample_3.txt, 04_i.txt, 04_p1.txt, 04_p2.txt, 04_random01.txt, 04_random02.txt, 04_random03.txt, 04_random04.txt, 04_random05.txt, 04_random06.txt, 04_random07.txt, 04_random08.txt, 04_random09.txt, 04_random10.txt, 04_random11.txt, 04_random12.txt, 04_random13.txt, 04_rp01.txt, 04_rp02.txt, 04_rp03.txt, 04_rp04.txt, 04_rp05.txt, 04_rp06.txt, 04_rp07.txt, 04_rp08.txt, 04_rp09.txt, 04_rp10.txt
Case Name Status Exec Time Memory
01_i.txt AC 1664 ms 86396 KB
01_random01.txt AC 1 ms 508 KB
01_random02.txt AC 1 ms 508 KB
01_random03.txt AC 2 ms 636 KB
01_random04.txt AC 55 ms 4476 KB
01_random05.txt AC 2683 ms 84348 KB
01_random06.txt AC 3173 ms 86396 KB
01_random07.txt AC 3239 ms 85372 KB
02_i.txt AC 7 ms 1404 KB
02_p.txt AC 8 ms 1404 KB
02_random01.txt AC 2 ms 508 KB
02_random02.txt AC 2 ms 508 KB
02_random03.txt AC 11 ms 1276 KB
02_random04.txt AC 7 ms 1404 KB
02_random05.txt AC 16 ms 1660 KB
02_random06.txt AC 23 ms 2044 KB
02_random07.txt AC 30 ms 2684 KB
02_random08.txt AC 30 ms 2812 KB
02_rp01.txt AC 8 ms 1404 KB
02_rp02.txt AC 9 ms 1404 KB
02_rp03.txt AC 8 ms 1404 KB
02_rp04.txt AC 8 ms 1404 KB
02_rp05.txt AC 9 ms 1404 KB
03_i.txt AC 2 ms 636 KB
03_random01.txt AC 3 ms 1020 KB
03_random02.txt AC 11 ms 1788 KB
03_random03.txt AC 10 ms 1660 KB
03_random04.txt AC 10 ms 1660 KB
03_random05.txt AC 3 ms 1020 KB
03_random06.txt AC 3 ms 1020 KB
03_random07.txt AC 4 ms 1148 KB
03_random08.txt AC 2 ms 1020 KB
03_random09.txt AC 5 ms 1148 KB
03_random10.txt AC 7 ms 1404 KB
03_random11.txt AC 11 ms 1660 KB
03_random12.txt AC 11 ms 1788 KB
03_random13.txt AC 9 ms 1532 KB
03_random14.txt AC 8 ms 1404 KB
03_random15.txt AC 4 ms 1148 KB
04_i.txt AC 1870 ms 86012 KB
04_p1.txt AC 2469 ms 83324 KB
04_p2.txt AC 1980 ms 63356 KB
04_random01.txt AC 1750 ms 49788 KB
04_random02.txt AC 1372 ms 39420 KB
04_random03.txt AC 286 ms 10620 KB
04_random04.txt AC 245 ms 8572 KB
04_random05.txt AC 396 ms 14716 KB
04_random06.txt AC 1914 ms 53884 KB
04_random07.txt AC 1128 ms 32508 KB
04_random08.txt AC 955 ms 27132 KB
04_random09.txt AC 499 ms 16764 KB
04_random10.txt AC 1860 ms 52988 KB
04_random11.txt AC 3402 ms 85756 KB
04_random12.txt AC 3439 ms 84988 KB
04_random13.txt AC 3357 ms 86652 KB
04_rp01.txt AC 2365 ms 85884 KB
04_rp02.txt AC 2343 ms 81660 KB
04_rp03.txt AC 2283 ms 84988 KB
04_rp04.txt AC 2421 ms 79228 KB
04_rp05.txt AC 2319 ms 84348 KB
04_rp06.txt AC 2471 ms 86652 KB
04_rp07.txt AC 2373 ms 86396 KB
04_rp08.txt AC 2522 ms 78204 KB
04_rp09.txt AC 2474 ms 80764 KB
04_rp10.txt AC 2399 ms 85884 KB
sample_1.txt AC 2 ms 508 KB
sample_2.txt AC 2 ms 508 KB
sample_3.txt AC 2 ms 764 KB