SHARE
TWEET

Untitled

a guest May 23rd, 2019 68 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  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. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top