Skip to content

Instantly share code, notes, and snippets.

@bryangarza

bryangarza/FilterElems.hs

Created November 10, 2015 05:35
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save bryangarza/b73fe04c3de8d02f5f86 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save bryangarza/b73fe04c3de8d02f5f86 to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. bryangarza created this gist Nov 10, 2015.
    43 changes: 43 additions & 0 deletions FilterElems.hs
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,43 @@
    module FilterElems where
    import Data.List
    import Control.Monad

    -- abstract tuple comparison
    sortTup f =
    case ord of
    EQ -> snd f
    _ -> ord
    where ord = fst f

    sortFst (a1,a2) (b1,b2) = sortTup ((compare a1 b1), (compare a2 b2))
    sortSnd (a1,a2) (b1,b2) = sortTup ((compare a2 b2), (compare a1 b1))
    eqSnd (_, x) (_, y) = x == y

    minI = minimum . map fst
    minIndex xs@(x:_) = (minI xs, snd x)

    (|>) = flip ($)
    infixl 0 |>

    findReps k xs =
    let xs' = xs |> zip [1..]
    |> sortBy sortSnd
    |> groupBy eqSnd
    |> filter ((>= k) . length)
    in case xs' of
    [] -> [-1]
    _ -> xs' |> map minIndex
    |> sortBy sortFst
    |> map snd

    readIntList :: IO [Int]
    readIntList = liftM (map read . words) getLine

    main :: IO ()
    main = do
    t <- readLn
    replicateM_ t $ do
    [_,k] <- readIntList
    as <- readIntList
    let ans = findReps k as
    putStrLn $ intercalate " " (map show ans)