Условие

Экзамен по берляндскому языку проходит в узкой и длинной аудитории. На экзамен пришло N студентов. Все они посажены в ряд. Таким образом, позиция каждого человека задается координатой на оси Ox (эта ось ведёт вдоль длинной аудитории). Два человека могут разговаривать, если расстояние между ними меньше или равно D. Какое наименьшее количество типов билетов должен подготовить преподаватель, чтобы никакие два студента с одинаковыми билетами не могли разговаривать? Выведите способ раздачи преподавателем билетов.

Примеры

Ввод: 4 1 11 1 12 2 Вывод:

2 1 1 2 2

Ввод: 4 0 11 1 12 2 Вывод:

1 1 1 1 1

Решение

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter
import java.util.HashMap
import kotlin.math.max

fun main() {
    val reader = BufferedReader(InputStreamReader(System.`in`))
    val writer = BufferedWriter(OutputStreamWriter(System.out))

    // Чтение количества студентов N и максимального расстояния D
    val firstLine = reader.readLine().split(" ")
    val n = firstLine[0].toInt()
    // Используем Long для D, чтобы избежать переполнения при вычитании координат,
    // хотя координаты и D сами по себе влезают в Int. Сравнение разницы с D будет надежнее.
    val d = firstLine[1].toLong()

    // Чтение координат студентов
    val coordinates = reader.readLine().split(" ").map { it.toInt() }

    // Создание списка пар (координата, исходный_индекс)
    val students = mutableListOf<Pair<Int, Int>>()
    for (i in 0 until n) {
        students.add(Pair(coordinates[i], i))
    }

    // Сортировка студентов по их координатам
    students.sortBy { it.first }

    // Массив для хранения результатов - назначенных номеров билетов.
    // Индексация соответствует исходному порядку студентов.
    val assignedTickets = IntArray(n)

    // Карта для хранения последней (самой правой) координаты,
    // где был использован каждый тип билета.
    // Ключ: номер билета (Int)
    // Значение: координата (Int)
    val lastUsedCoordinate = HashMap<Int, Int>()

    // Определяем "безопасное" значение для координаты, которое гарантированно
    // находится на расстоянии > D от любой реальной координаты (которые >= 0).
    // Если d=0, то lastCoord = -1. currentCoord - (-1) > 0.
    // Если d > 0, то lastCoord = -1-d. currentCoord - (-1-d) = currentCoord + 1 + d > d.
    val veryFarAwayCoordinate = -1L - d // Используем Long для согласованности

    // Переменная для отслеживания максимального номера билета, который понадобился.
    var maxTicketUsed = 0

    // Обработка каждого студента в порядке возрастания их координат
    for (studentData in students) {
        val currentCoord = studentData.first // Координата текущего студента
        val originalIndex = studentData.second // Исходный индекс текущего студента

        var currentTicket = 1 // Начинаем подбирать билет с номера 1
        while (true) {
            // Получаем координату последнего студента, которому был выдан билет currentTicket.
            // Если билет еще не выдавался, используем veryFarAwayCoordinate.
            val lastCoord = lastUsedCoordinate.getOrDefault(currentTicket, veryFarAwayCoordinate.toInt())

            // Проверяем условие: можно ли выдать билет currentTicket?
            // Можно, если расстояние между текущим студентом (currentCoord) и
            // последним студентом с таким же билетом (lastCoord) строго больше D.
            // currentCoord >= lastCoord, так как мы идем по отсортированным координатам.
            if (currentCoord.toLong() - lastCoord.toLong() > d) {
                 // Нашли подходящий билет, выходим из цикла подбора
                 break
            }

            // Если текущий номер билета не подходит (слишком близко),
            // пробуем следующий номер билета.
            currentTicket++
        }

        // Назначаем найденный номер билета студенту с исходным индексом originalIndex
        assignedTickets[originalIndex] = currentTicket

        // Обновляем информацию о последнем использовании билета currentTicket
        lastUsedCoordinate[currentTicket] = currentCoord

        // Обновляем максимальный номер использованного билета, если нужно
        maxTicketUsed = max(maxTicketUsed, currentTicket)
    }

    // Вывод результатов:
    // 1. Минимальное количество типов билетов (равное максимальному использованному номеру)
    writer.write("$maxTicketUsed\\n")
    // 2. Номера билетов для каждого студента в их исходном порядке
    writer.write(assignedTickets.joinToString(" "))
    writer.newLine() // Перевод строки в конце вывода

    reader.close()
    writer.close()
}