Advertisement
nachtvaohal

contests

Jan 18th, 2024 (edited)
75
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Kotlin 1.60 KB | None | 0 0
  1. import kotlin.math.max
  2.  
  3. fun findMaxDrawSequenceLinear2(results: List<Int>): Int {
  4.     val gapToItsFirstOccurrence = mutableMapOf<Int, Int>()
  5.     var maxLength = 0
  6.     // Разница в очках. 0 означает ничью.
  7.     var gap = 0
  8.     // изначально у нас ничья для полуинтервала [0;0)
  9.     gapToItsFirstOccurrence[gap] = 0
  10.  
  11.     // Начинаем с единицы, полуинтервал не включает в себя правое значение i
  12.     for (i in 1..results.size) {
  13.         val temp = results[i - 1]
  14.         if (temp == 0) {
  15.             gap--
  16.         } else if (temp == 1) {
  17.             gap++
  18.         }
  19.         // Идея в том, что самая длинная ничейная сессия будет равна максимальной длине полуинтервала, у которого
  20.         // совпадает разница в начале полуинтервала и для каждого уникального значения разницы будет сохраняться
  21.         // индекс начала полуинтервала
  22.         val firstOccurrence = gapToItsFirstOccurrence.getOrPut(gap) { i }
  23.         maxLength = max(maxLength, (i - firstOccurrence))
  24.     }
  25.     return maxLength
  26. }
  27.  
  28. fun main() {
  29.     val reader = System.`in`.bufferedReader()
  30.     val count = reader.readLine().toInt()
  31.     if (count == 0) {
  32.         println(0)
  33.     } else {
  34.         val input = reader.readLine().split(" ")
  35.             .map { it.toInt() }
  36.         println(findMaxDrawSequenceLinear2(input))
  37.     }
  38. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement