Advertisement
Guest User

Untitled

a guest
May 23rd, 2019
89
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.48 KB | None | 0 0
  1. package icpc.finals.f2019
  2.  
  3. import java.io.BufferedReader
  4. import java.io.File
  5. import java.io.InputStreamReader
  6. import java.util.*
  7.  
  8. fun main() {
  9. val br = File("/Users/z00327d/src/tools/icpc/src/A-azulejos/secret-05.in").bufferedReader()
  10. // val br = BufferedReader(InputStreamReader(System.`in`))
  11. val n = br.readLine().toInt()
  12. val bpArr = br.readLine().split(" ").map { it.toInt() }
  13. val bhArr = br.readLine().split(" ").map { it.toInt() }
  14. val fpArr = br.readLine().split(" ").map { it.toInt() }
  15. val fhArr = br.readLine().split(" ").map { it.toInt() }
  16.  
  17. val backTree: SortedMap<Int, TreeSet<Tile>> = sortedMapOf()
  18. val frntTree: SortedMap<Int, TreeSet<Tile>> = sortedMapOf()
  19.  
  20. for (i in 0 until n) {
  21. backTree.getOrPut(bpArr[i]) { sortedSetOf() }
  22. .add(Tile(i + 1, bpArr[i], bhArr[i]))
  23. frntTree.getOrPut(fpArr[i]) { sortedSetOf(reverseOrder()) }
  24. .add(Tile(i + 1, fpArr[i], fhArr[i]))
  25. }
  26.  
  27. var bPricePoint = backTree.pop()
  28. var fPricePoint = frntTree.pop()
  29. val bOut = mutableListOf<Int>()
  30. val fOut = mutableListOf<Int>()
  31. for (i in 0 until n) {
  32. if (bPricePoint.isEmpty()) {
  33. bPricePoint = backTree.pop()
  34. }
  35. if (fPricePoint.isEmpty()) {
  36. fPricePoint = frntTree.pop()
  37. }
  38. var bTile: Tile?
  39. var fTile: Tile?
  40. if (bPricePoint.size > fPricePoint.size) {
  41. bTile = bPricePoint.pollLast()
  42. fTile = fPricePoint.pop(bTile)
  43. } else {
  44. fTile = fPricePoint.pollFirst()
  45. bTile = bPricePoint.pop(fTile)
  46. }
  47. if (bTile == null || fTile == null || fTile.height >= bTile.height) {
  48. println("impossible")
  49. return
  50. }
  51. bOut += bTile.id
  52. fOut += fTile.id
  53. }
  54. for (idx in bOut) {
  55. print("$idx ")
  56. }
  57. println()
  58. for (idx in fOut) {
  59. print("$idx ")
  60. }
  61. }
  62.  
  63. private fun SortedMap<Int, TreeSet<Tile>>.pop(): TreeSet<Tile> {
  64. return this.remove(this.firstKey())!!
  65. }
  66.  
  67. private fun TreeSet<Tile>.pop(tile: Tile): Tile? {
  68. val newTile = this.higher(tile)
  69. if (newTile != null)
  70. this.remove(newTile)
  71. return newTile
  72. }
  73.  
  74. data class Tile(val id: Int, val price: Int, val height: Int) : Comparable<Tile> {
  75. override fun compareTo(other: Tile): Int {
  76. if (height == other.height) return id.compareTo(other.id)
  77. return height.compareTo(other.height)
  78. }
  79. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement