package com.yoavst.testing

import java.io.File
import java.util.*
import kotlin.math.absoluteValue
import kotlin.math.max

interface Locatable {
    val x: Int
    val y: Int
}

data class Location(override val x: Int, override val y: Int) : Locatable {
    override fun toString(): String = "($x,$y)"
    companion object {
        val Zero = Location(0, 0)
    }
}

data class Trip(val id: Int, val start: Location, val end: Location, val startTime: Int, val finishTime: Int) {
    val distance = dist(start, end)
}

class Car(val id: Int, val rides: MutableList<Trip> = ArrayList(), var nextEndTime: Int = 0) : Locatable, Comparable<Car> {
    var location: Location = Location.Zero
    override val x: Int
        get() = location.x
    override val y: Int
        get() = location.y

    override fun equals(other: Any?): Boolean = other is Car && other.id == id
    override fun hashCode(): Int = id
    override fun compareTo(other: Car): Int = nextEndTime - other.nextEndTime
}

fun dist(loc1: Locatable, loc2: Locatable): Int = (loc1.x - loc2.x).absoluteValue + (loc1.y - loc2.y).absoluteValue

private var lastTime: Long = 0
fun tick(name: String) {
    val current = System.currentTimeMillis()
    if (lastTime == 0L) {
        println("Starting count: $name, Time now: $current")
    } else {
        println("$name, Time now: $current, Delta: ${current - lastTime}")
    }
    lastTime = current
}

fun main(args: Array<String>) {
    val start = System.currentTimeMillis()
    tick("Starting")
    val inFile = File("a.in")
    val outFile = File("a.out")
    inFile.reader().useLines { lines ->
        val iter = lines.iterator()
        val (r, c, f, n, b, t) = iter.next().split(" ")
        val carsCount = f.toInt()
        val bonus = b.toInt()
        val steps = t.toInt()
        val rides = n.toInt()
        val initialTrips: MutableList<Trip> = ArrayList(rides)
        for ((i, line) in iter.withIndex()) {
            val data = line.split(' ', limit = 6)
            initialTrips += Trip(i, Location(data[0].toInt(), data[1].toInt()), Location(data[2].toInt(), data[3].toInt()), data[4].toInt(), data[5].toInt())
        }
        tick("Loaded from file")

        val queue = PriorityQueue<Car>(carsCount)
        val cars = ArrayList<Car>(carsCount)
        repeat(carsCount) { id ->
            val car = Car(id)
            queue += car
            cars += car
        }
        tick("Loaded into the queue")

        val trips = filterImpossibleTrips(initialTrips, cars, 0, byEndTime = true, byBonus = false)
        tick("Filtered impossible trips")

        var currentTurn = 0
        var finishedYet = 1
        tick("Starting the fun")
        while (currentTurn < steps && cars.isNotEmpty() && trips.isNotEmpty()) {
            val car = queue.poll()
            currentTurn = car.nextEndTime

            finishedYet++
            if (finishedYet % 300 == 0) {
                tick("Reached: $finishedYet")
            }

            val ride = bestTripForCar(car, trips, currentTurn, bonus)
            if (ride != null) {
                assignRideToCar(car, ride, currentTurn)
                trips.remove(ride)
                queue += car
            }
        }

        tick("Done!")
        outFile.printWriter().use { writer ->
            for (car in cars) {
                writer.write(car.rides.size.toString())
                writer.write(" ")
                for (ride in car.rides) {
                    writer.write("${ride.id} ")
                }
                writer.println()
            }
        }
        tick("Realy really done!")
    }
    val end = System.currentTimeMillis()
    println("Total time: ${end - start}ms")
}

private fun points(loc: Locatable, trip: Trip, currentTurn: Int, bonus: Int): Int {
    val d = dist(loc, trip.start)
    if (d + trip.distance + currentTurn > trip.finishTime)
        return 0
    else if (d + currentTurn < trip.startTime)
        return bonus + trip.distance
    return trip.distance
}

private fun bestEndTime(loc: Locatable, trip: Trip, currentTurn: Int): Int = max(trip.startTime, currentTurn + dist(loc, trip.start)) + trip.distance

private fun bestTripForCar(car: Car, trips: List<Trip>, currentTurn: Int, bonus: Int): Trip? {
    val trip = trips.minBy { trip ->
        val points = points(car, trip, currentTurn, bonus)
        if (points == 0)
            Int.MAX_VALUE
        else
            score(bestEndTime(car, trip, currentTurn), points, currentTurn)
    }!!
    return trip.takeIf { points(car, it, currentTurn, bonus) > 0 }
}

private fun assignRideToCar(car: Car, ride: Trip, currentTurn: Int) {
    car.rides += ride
    car.nextEndTime = bestEndTime(car, ride, currentTurn)
    car.location = ride.end
}

private inline fun score(time: Int, points: Int, currentTurn: Int) = (time - currentTurn) - points

private fun filterImpossibleTrips(trips: List<Trip>, cars: List<Locatable>, currentTurn: Int, byEndTime: Boolean, byBonus: Boolean): MutableList<Trip> {
    val filtered = ArrayList<Trip>(trips.size)
    for (trip in trips) {
        val start = trip.start
        val distance = dist(cars.minBy { dist(it, start) }!!, start)
        if (byBonus && distance + trip.startTime > trip.finishTime)
            continue
        if (byEndTime && max(trip.startTime, currentTurn + distance) + trip.distance > trip.finishTime)
            continue
        filtered += trip
    }
    return filtered
}

operator fun <T> List<T>.component6(): T = get(5)