Advertisement
Guest User

Untitled

a guest
Nov 5th, 2018
74
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Kotlin 2.55 KB | None | 0 0
  1. import java.io.BufferedWriter
  2. import java.nio.file.Files
  3. import java.nio.file.Paths
  4. import java.util.*
  5.  
  6.  
  7. /**
  8.  * Created by damm1t.
  9.  */
  10. var MAXN: Int = 1005
  11. var t = Array(MAXN) {IntArray(MAXN)}
  12. var inserted = BooleanArray(MAXN) {false}
  13. var mas = mutableListOf<Int>()
  14.  
  15. fun merge(mas: ArrayList<Int>, l: Int, middle: Int, r: Int) {
  16.     var i = 0
  17.     var j = 0
  18.     var k: Int = l
  19.     val sizeLeft = middle - l + 1
  20.     val sizeRight = r - middle
  21.     val left = ArrayList<Int>()
  22.     val right = ArrayList<Int>()
  23.  
  24.     while (i < sizeLeft) {
  25.         left.add(mas[l + i])
  26.         i++
  27.     }
  28.     while (j < sizeRight) {
  29.         right.add(mas[middle + 1 + j])
  30.         j++
  31.     }
  32.     i = 0
  33.     j = 0
  34.     while (i < sizeLeft && j < sizeRight) {
  35.         if (t[left[i]][right[j]] == 1) {
  36.             mas[k] = left[i]
  37.             i++
  38.         } else {
  39.             mas[k] = right[j]
  40.             j++
  41.         }
  42.         k++
  43.     }
  44.     while (i < sizeLeft) {
  45.         mas[k] = left[i]
  46.         i++
  47.         k++
  48.     }
  49.     while (j < sizeRight) {
  50.         mas[k] = right[j]
  51.         j++
  52.         k++
  53.     }
  54. }
  55.  
  56. fun mergeSort(mas: ArrayList<Int>, l: Int, r: Int) {
  57.     if (l < r) {
  58.         val m = l + (r - l) / 2
  59.         mergeSort(mas, l, m)
  60.         mergeSort(mas, m + 1, r)
  61.         merge(mas, l, m, r)
  62.     }
  63. }
  64.  
  65. fun main(args: Array<String>) {
  66.     val file = "guyaury"
  67.  
  68.     Files.newBufferedReader(Paths.get("$file.in")).use { fin ->
  69.         var n = fin.readLine().toInt()
  70.         mas.add(0)
  71.         inserted[0] = true
  72.         t[0][0] = 2
  73.         for (i in 0 until n)
  74.         {
  75.             t[i][i] = 2
  76.             val ch = fin.readLine()
  77.             for (j in 0 until i)
  78.             {
  79.                 t[i][j] = ch[j].toInt() - 48
  80.                 t[j][i] = t[i][j] xor 1
  81.             }
  82.         }
  83.         val vertex = ArrayList<Int>()
  84.  
  85.         for (i in 0 until n) {
  86.             vertex.add(i)
  87.         }
  88.         mergeSort(vertex, 0, n - 1)
  89.         Files.newBufferedWriter(Paths.get("$file.out")).use { fout ->
  90.             while (t[vertex[n - 1]][vertex[0]] != 1) {
  91.                 vertex.shuffle()
  92.                 mergeSort(vertex, 0, n - 1)
  93.             }
  94.             for (i in 0 until n) {
  95.                 fout.writeSpace(vertex[i] + 1)
  96.             }
  97.         }
  98.     }
  99. }
  100.  
  101. private fun BufferedWriter.writeLine(s: String) {
  102.     this.write(s)
  103.     this.write("\n")
  104. }
  105.  
  106. private fun BufferedWriter.writeSpace(s: Int) {
  107.     this.write(s.toString() + ' ')
  108. }
  109.  
  110. private fun BufferedWriter.writeLine(s: Int) {
  111.     this.writeLine(s.toString())
  112. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement