Sorting.scala

import scala.io.Source
import java.io.{ File, PrintStream }

object Sorting {
  implicit def convert( value : Tuple2[Int, Int]) = ValueAndIndex(value._1, value._2)
  case class ValueAndIndex(value:Int, index:Int)
  
  def sorting ( arr : List[Int]) : List[Int] = {
    def isEven (x:Int):Boolean = {x % 2 == 0}
    val (bobEven, alexOdd) = arr.partition(isEven)
    val (evenIndexs, oddIndexs) = arr.zipWithIndex.partition(x => isEven(x.value))
    
    (alexOdd.sorted.zip(oddIndexs.map(_.index)) ++ bobEven.sorted.reverse.zip(evenIndexs.map(_.index))).sortBy(_.index).map(_.value)
  }
  
  def process(iter: Iterator[String])(pr: String => Unit) {
    for (i <- 1 to iter.next().toInt) yield {
      iter.next()
      val line = iter.next().split(' ').map(_.toInt)
      pr(s"Case #$i: ${sorting(line.toList).mkString(" ")}")
    }
  }

  def main(args: Array[String]) {
    val in = Source.fromFile(new File("test.in"))
    val out = new PrintStream(new File("a.out"))
    try {
      process(in.getLines) { s: String => println(s) }
    } finally {
      out.flush; out.close
    }
  }
}