def isEmpty
= items.
isEmpty case n
=> items.
updated(item, n -
1) })
}
def apply
[E
](items
: Traversable
[E
]): Bag
[E
] = { val itemCounts
= mutable.
HashMap.
empty[E, Int
].
withDefaultValue(0) items.foreach(itemCounts(_) += 1)
}
}
def solve
(items
: Bag
[String
], anagrams
: String
) = { def branch
(trial
: String, position
: Int, candidates
: Bag
[String
]): Option
[Seq
[(String, String
)]] = { val label
= anagrams.
substring(position, position + trial.
length) if (trial
== label.
sorted) { if (candidates.
isEmpty) Option
(Seq
((trial, label
))) .map(newTrial => branch(newTrial, position + trial.length, candidates - newTrial))
.find(_.isDefined).flatten.map((trial, label) +: _)
}
items.view.map(item => branch(item, 0, items - item)).find(_.isDefined).flatten
}
val items
= readLine
().
split(" ") val anagrams
= readLine
()
val sortedItems
= mutable.
Buffer.
empty[String
] val itemOrderRestorator
= mutable.
Map.
empty[String, mutable.
Queue[String
]]
sortedItems += sorted
itemOrderRestorator.
getOrElseUpdate(sorted,
new mutable.
Queue).
enqueue(item
) }
solve
(Bag
(sortedItems
), anagrams
) match { case None
=> println
("Ne fart") val (items, labels
) = solution.
unzip labels.foreach(s => print(s + " "))
println()
items.foreach(s => print(itemOrderRestorator(s).dequeue() + " "))
}
}
aW1wb3J0IHNjYWxhLmNvbGxlY3Rpb24uXwoKY2xhc3MgQmFnW0VdIHByaXZhdGUgKHZhbCBpdGVtczogTWFwW0UsIEludF0pIHsKICBkZWYgaXNFbXB0eSA9IGl0ZW1zLmlzRW1wdHkKICBkZWYgdmlldyA9IGl0ZW1zLmtleXMKICBkZWYgLShpdGVtOiBFKSA9IG5ldyBCYWdbRV0oaXRlbXMoaXRlbSkgbWF0Y2ggewogICAgY2FzZSAxID0+IGl0ZW1zIC0gaXRlbQogICAgY2FzZSBuID0+IGl0ZW1zLnVwZGF0ZWQoaXRlbSwgbiAtIDEpCiAgfSkKfQoKb2JqZWN0IEJhZyB7CiAgZGVmIGFwcGx5W0VdKGl0ZW1zOiBUcmF2ZXJzYWJsZVtFXSk6IEJhZ1tFXSA9IHsKICAgIHZhbCBpdGVtQ291bnRzID0gbXV0YWJsZS5IYXNoTWFwLmVtcHR5W0UsIEludF0ud2l0aERlZmF1bHRWYWx1ZSgwKQogICAgaXRlbXMuZm9yZWFjaChpdGVtQ291bnRzKF8pICs9IDEpCiAgICBuZXcgQmFnW0VdKGl0ZW1Db3VudHMpCiAgfQp9CgpvYmplY3QgTWFpbiBleHRlbmRzIEFwcCB7CiAgZGVmIHNvbHZlKGl0ZW1zOiBCYWdbU3RyaW5nXSwgYW5hZ3JhbXM6IFN0cmluZykgPSB7CiAgICBkZWYgYnJhbmNoKHRyaWFsOiBTdHJpbmcsIHBvc2l0aW9uOiBJbnQsIGNhbmRpZGF0ZXM6IEJhZ1tTdHJpbmddKTogT3B0aW9uW1NlcVsoU3RyaW5nLCBTdHJpbmcpXV0gPSB7CiAgICAgIHZhbCBsYWJlbCA9IGFuYWdyYW1zLnN1YnN0cmluZyhwb3NpdGlvbiwgcG9zaXRpb24gKyB0cmlhbC5sZW5ndGgpCiAgICAgIGlmICh0cmlhbCA9PSBsYWJlbC5zb3J0ZWQpIHsKICAgICAgICBpZiAoY2FuZGlkYXRlcy5pc0VtcHR5KSBPcHRpb24oU2VxKCh0cmlhbCwgbGFiZWwpKSkKICAgICAgICBlbHNlIGNhbmRpZGF0ZXMudmlldwogICAgICAgICAgLm1hcChuZXdUcmlhbCA9PiBicmFuY2gobmV3VHJpYWwsIHBvc2l0aW9uICsgdHJpYWwubGVuZ3RoLCBjYW5kaWRhdGVzIC0gbmV3VHJpYWwpKQogICAgICAgICAgLmZpbmQoXy5pc0RlZmluZWQpLmZsYXR0ZW4ubWFwKCh0cmlhbCwgbGFiZWwpICs6IF8pCiAgICAgIH0gZWxzZSBOb25lCiAgICB9CiAgICBpdGVtcy52aWV3Lm1hcChpdGVtID0+IGJyYW5jaChpdGVtLCAwLCBpdGVtcyAtIGl0ZW0pKS5maW5kKF8uaXNEZWZpbmVkKS5mbGF0dGVuCiAgfQoKICB2YWwgaXRlbXMgPSByZWFkTGluZSgpLnNwbGl0KCIgIikKICB2YWwgYW5hZ3JhbXMgPSByZWFkTGluZSgpCgogIHZhbCBzb3J0ZWRJdGVtcyA9IG11dGFibGUuQnVmZmVyLmVtcHR5W1N0cmluZ10KICB2YWwgaXRlbU9yZGVyUmVzdG9yYXRvciA9IG11dGFibGUuTWFwLmVtcHR5W1N0cmluZywgbXV0YWJsZS5RdWV1ZVtTdHJpbmddXQoKICBmb3IgKGl0ZW0gPC0gaXRlbXMpIHsKICAgIHZhbCBzb3J0ZWQgPSBpdGVtLnNvcnRlZAogICAgc29ydGVkSXRlbXMgKz0gc29ydGVkCiAgICBpdGVtT3JkZXJSZXN0b3JhdG9yLmdldE9yRWxzZVVwZGF0ZShzb3J0ZWQsIG5ldyBtdXRhYmxlLlF1ZXVlKS5lbnF1ZXVlKGl0ZW0pCiAgfQoKICBzb2x2ZShCYWcoc29ydGVkSXRlbXMpLCBhbmFncmFtcykgbWF0Y2ggewogICAgY2FzZSBOb25lID0+IHByaW50bG4oIk5lIGZhcnQiKQogICAgY2FzZSBTb21lKHNvbHV0aW9uKSA9PgogICAgICB2YWwgKGl0ZW1zLCBsYWJlbHMpID0gc29sdXRpb24udW56aXAKICAgICAgbGFiZWxzLmZvcmVhY2gocyA9PiBwcmludChzICsgIiAiKSkKICAgICAgcHJpbnRsbigpCiAgICAgIGl0ZW1zLmZvcmVhY2gocyA9PiBwcmludChpdGVtT3JkZXJSZXN0b3JhdG9yKHMpLmRlcXVldWUoKSArICIgIikpCiAgfQp9