fork(1) download
  1. import scala.collection._
  2.  
  3. class Bag[E] private (val items: Map[E, Int]) {
  4. def isEmpty = items.isEmpty
  5. def view = items.keys
  6. def -(item: E) = new Bag[E](items(item) match {
  7. case 1 => items - item
  8. case n => items.updated(item, n - 1)
  9. })
  10. }
  11.  
  12. object Bag {
  13. def apply[E](items: Traversable[E]): Bag[E] = {
  14. val itemCounts = mutable.HashMap.empty[E, Int].withDefaultValue(0)
  15. items.foreach(itemCounts(_) += 1)
  16. new Bag[E](itemCounts)
  17. }
  18. }
  19.  
  20. object Main extends App {
  21. type Solution = Option[Seq[(String, String)]]
  22.  
  23. def solve(items: Bag[String], anagrams: String, matches: Solution = None): Solution =
  24. if (items.isEmpty) matches
  25. else (for {
  26. item <- items.view
  27. (label, rest) = anagrams.splitAt(item.length)
  28. if item == label.sorted
  29. newMatches = Option(matches.getOrElse(immutable.Queue.empty) :+ (item, label))
  30. solution <- solve(items - item, rest, newMatches)
  31. } yield solution).headOption
  32.  
  33. val items = readLine().split(" ")
  34. val anagrams = readLine()
  35.  
  36. val sortedItems = mutable.Buffer.empty[String]
  37. val itemOrderRestorator = mutable.Map.empty[String, mutable.Queue[String]]
  38.  
  39. for (item <- items) {
  40. val sorted = item.sorted
  41. sortedItems += sorted
  42. itemOrderRestorator.getOrElseUpdate(sorted, new mutable.Queue).enqueue(item)
  43. }
  44.  
  45. solve(Bag(sortedItems), anagrams).map(_.unzip) match {
  46. case None => println("Ne fart")
  47. case Some((items, labels)) =>
  48. println(labels.mkString(" "))
  49. items.foreach(s => print(itemOrderRestorator(s).dequeue() + " "))
  50. }
  51. }
Runtime error #stdin #stdout #stderr 4.99s 382272KB
stdin
abcabc abc bc abc abcabc abc bc abc abcabc abc bc abc abcabc abc bc abc abcabc abc bc abc
abcabcabcbcabcabcabcabcbcabcabcabcabcbcabcabcabcabcbcabcabcabcabcbcabc
stdout
Standard output is empty
stderr
/spoj/scala_run: line 3:  7041 CPU time limit exceeded /opt/java/bin/java -client -Xmx256M -Xms16M -Xbatch -Dfile.encoding=UTF-8 -jar $1