Fairland.scala

import java.io.FileOutputStream

import scala.io.Source

object Fairland {
  val INPUT = "A-large-practice.in"
  val OUTPUT = INPUT.takeWhile(_ != '.') + ".out"
  val isConsole = true

  def main(args: Array[String]): Unit = {
    val itr = Source.fromFile(INPUT).getLines()
    val stream = if (isConsole) Console.out else new FileOutputStream(OUTPUT)
    try {
      Console.withOut(stream) {
        val sets = itr.next().toInt
        (1 to sets).foreach { set =>
          val Array(n, d) = itr.next().split(' ').map(_.toInt)
          val Array(sInit, as, cs, rs) = itr.next().split(' ').map(_.toInt)
          val Array(mInit, am, cm, rm) = itr.next().split(' ').map(_.toInt)

          var sBefore = sInit
          var mBefore = mInit

          val vector = for {
            i <- (1 until n).toVector
          } yield {
              mBefore = (mBefore * am + cm) % rm
              sBefore = (sBefore * as + cs) % rs
              (i, mBefore % i, sBefore)
            }
          val allVector = (0, -1, sInit) +: vector

          println(f"Case #$set: ${numberOfEmployeee(allVector, d)}")
        }
      }
    } finally {
      stream.flush()
      if (!isConsole) stream.close()
    }
  }


  /**
   * @note recursive 하게 depth first search를 하였을 경우 large data set에서 overflow 발생.
   *       최대한 원래 소스를 변경하지 않는 범위에서 tail recursion이 되도록 변경해봄.(느려요...)
   */
  def search(map: Map[Int, Vector[(Int, Int, Int)]], stream: Vector[(Int, Int, Int)], d: Int, accr: Vector[(Int, Int)]): Vector[(Int, Int)] = stream match {
    case Vector() => accr
    case (current, mMin, mMax) +: xs if map.isDefinedAt(current) =>
      val list: collection.mutable.ListBuffer[(Int, Int)] = collection.mutable.ListBuffer()
      val newStream = for {
        (id,bossId,salary) <- map(current) if salary + d >= mMin && salary <= mMax
      } yield {
        val newMin = salary max mMin
        val newMax = mMax min salary + d
        list.prepend((newMin, 1), (newMax + 1, -1))
        (id, newMin, newMax)
      }
      search(map, xs ++ newStream, d, accr ++ list)
    case x +: xs => search(map, xs, d, accr)
  }


  def numberOfEmployeee(vector: Vector[(Int, Int, Int)], d: Int) = {
    val childVector = vector.tail.groupBy(_._2).toMap

    val mMin = vector.head._3
    val mMax = vector.head._3 + d

    val ret: Vector[(Int, Int)] = (mMin, 1) +: (mMax + 1, -1) +: search(childVector, Vector((0, mMin, mMax)), d, Vector())
    //같은 지점의 증감을 모두 합한다.
    val grouped = ret.groupBy(_._1).map {
      case (key, list) => (key, list.map(_._2).sum)
    }.toVector.sortBy(_._1)

    grouped.foldLeft((0, 0)) {
      case ((max, current), (_, variation)) =>
        val m = current + variation
        (max max m, m)
    }._1
  }
}