findmin.scala

import scala.io.Source
import java.io.PrintWriter
import scala.collection.mutable.Queue
import scala.collection.mutable.BitSet
import scala.collection.mutable.Map

object findmin extends App {
  
  def rfm(j: Int, n: Int, k: Int, m: Queue[Int], mm: Map[Int,Int], csm:BitSet): Int = {
    if (j==n) m.last
    else if (j > 2*k){
      m += csm.head
      m( (k+(n-j)-1) % (k+1) )
    } 
    else {
      val min = csm.head
      val out = m.dequeue
      m += min
      
      csm -= min
      
      if (mm.contains(min)) mm.update(min, mm.get(min).get+1)
      else mm.put(min, 1)
      
      val oc = mm.get(out).get
      if (oc == 1) { 
        csm += out
        mm.remove(out)
      }
      else mm.update(out, oc-1)
      
      rfm(j+1, n, k, m , mm, csm)
      
//      if (m.contains(out)) rfm(j+1, n, k, m , mm, csm -= min )
//      else rfm(j+1, n, k, m , mm, (csm += out) -= min )
    }
  }
  
  def complement(m:Queue[Int], k:Int): BitSet = {
    var c = BitSet.empty
    for ( i <- k to 0 by -1 ) c += i
    for ( e <- m ) c -= e
    c
  }

  def genFirstK(k: Int, a: Int, b: Int, c: Int, r: Int): Queue[Int] = {
    val m = new Array[Int](k)
    m(0) = a
    for (val i <- 1 until k) m(i) = ((b.toLong*m(i-1).toLong+c.toLong)%r.toLong).toInt
    Queue.empty[Int] ++= m
  }
  
  def findMin(n:Int, k:Int, a:Int, b:Int, c:Int, r:Int): Int = {
    val m = genFirstK(k,a,b,c,r)
    val mm = Map.empty[Int,Int] ++ m.groupBy(n=>n).mapValues(l => l.length)
    val csm = complement(m,k)
    rfm(k,n,k,m,mm,csm)
  }
  
  def consolidate(dp: List[String], acc: List[String]): List[String] = {
    if (dp.isEmpty) acc
    else consolidate(dp drop 2, acc :+ dp(0)++" "+dp(1))
  }
  
  def dispatchSolving(s: String): Long = {
    val tokens = s.split(' ') map (_.toInt)
    findMin(tokens(0),tokens(1),tokens(2),tokens(3),tokens(4),tokens(5))
  }
  
  val input = Source.fromFile("input")
  val output = new PrintWriter("output")
  
  val lines = input.getLines.toList
  val n = (lines take 1)(0).toInt
  val problem_strings = lines drop 1
  val problems = consolidate(problem_strings,List())
  
  val startTime = System.currentTimeMillis
  val results = (problems.par map dispatchSolving).toList
  val elapsedTime = System.currentTimeMillis - startTime
  
  println("Elapsed Time: " + elapsedTime/60000 + "m " + (elapsedTime%60000)/1000 + "s " + elapsedTime%1000 + "ms" );
  
  val lp = ( (1 to n).toList,problems,results ).zipped.toList map { case (n, problem, result) => output.println("Case #" + n + ": " + result) }
  
  input.close
  output.close
}