Generate (somewhat hard) test cases for ABC070 D

abc070-killer.hs

-- Generate (somewhat hard) test cases for ABC070 D
-- https://atcoder.jp/contests/abc070/tasks/abc070_d
module Main (main) where

type Input = (Int, [(Int, Int, Int)], Int, [(Int, Int)])

main :: IO ()
main = do
  writeInputTo "abc070-d-10k-path.txt" (largePathGraph 10000)
  writeInputTo "abc070-d-20k-path.txt" (largePathGraph 20000)
  writeInputTo "abc070-d-40k-path.txt" (largePathGraph 40000)
  writeInputTo "abc070-d-large-path.txt" (largePathGraph 100000)
  writeInputTo "abc070-d-large-star.txt" (largeStarGraph 100000)

writeInputTo :: FilePath -> Input -> IO ()
writeInputTo path (n, abcs, k, xys) = do
  let q = length xys
  writeFile path $ unlines $ show n : map showTriple abcs ++ [showPair (q,k)] ++ map showPair xys
  putStrLn $ "Input written to " ++ path
  where
    showTriple (a, b, c) = unwords [show a, show b, show c]
    showPair (x, y) = unwords [show x, show y]

qMax :: Int
qMax = 100000

largePathGraph :: Int -> Input
largePathGraph n = (n, abcs, 1, xys)
  where
    abcs = [(i, i + 1, i) | i <- [1 .. n - 1]]
    xys = [(modN i, modN $ i + 1) | i <- [1 .. qMax]]
    modN j = (j - 1) `mod` n + 1

largeStarGraph :: Int -> Input
largeStarGraph n = (n, abcs, 1, xys)
  where
    abcs = [(1, i, i) | i <- [2 .. n]]
    xys = [(modN i, modN $ i + 1) | i <- [1 .. qMax]]
    modN j = (j - 1) `mod` n + 1