package main import ( "fmt" "os" "sort" ) var input *os.File var output *os.File var R int var C int var F int var N int var B int var T int var Rides []*Ride var Cars []*Car var Sched Scheduler type Ride struct { ID int a, b, x, y, s, f int used bool } func (r Ride) Length() int { xdist := r.a - r.x if xdist < 0 { xdist = -xdist } ydist := r.b - r.y if ydist < 0 { ydist = -ydist } return xdist + ydist } func abs(x int) int { if x < 0 { return -x } else { return x } } func (r *Ride) length() int { return abs(r.a-r.x) + abs(r.b-r.y) } type ByEndtime []*Ride func (rs ByEndtime) Len() int { return len(rs) } func (rs ByEndtime) Swap(i, j int) { rs[i], rs[j] = rs[j], rs[i] } func (rs ByEndtime) Less(i, j int) bool { return rs[i].f < rs[j].f || (rs[i].f == rs[j].f && rs[i].length() < rs[j].length()) } type Scheduler interface { Add(*Car) Pop() *Car } type Car struct { ID int Rides []int Arrival int X int Y int } func (c *Car) Update(r *Ride) { c.moveTo(r.a, r.b) if c.Arrival < r.s { c.Arrival = r.s } c.moveTo(r.x, r.y) c.Rides = append(c.Rides, r.ID) } func (c *Car) EarliestFinish(r *Ride) int { copy := &Car{ Arrival: c.Arrival, X: c.X, Y: c.Y, } copy.moveTo(r.a, r.b) if copy.Arrival < r.s { copy.Arrival = r.s } copy.moveTo(r.x, r.y) return copy.Arrival } func (c *Car) moveTo(x, y int) { xdist := c.X - x if xdist < 0 { xdist = -xdist } ydist := c.Y - y if ydist < 0 { ydist = -ydist } c.Arrival += xdist + ydist c.X = x c.Y = y } func (c *Car) distanceTo(x, y int) int { return abs(c.X-x) + abs(c.Y-y) } func max(a, b int) int { if a > b { return a } else { return b } } func Choose(c *Car) *Ride { var bestRide *Ride bestLenOfRide := 0 bestTotal := 0 // fmt.Printf("car %d\n", c.ID) for _, r := range Rides { if r.used { continue } if r.Length() > 6000 { continue } if r.f < c.EarliestFinish(r) { continue } // fmt.Printf("%d %d -> %d %d\n", r.a, r.b, r.x, r.y) lenOfRide := r.length() total := max(c.distanceTo(r.a, r.b), r.s-c.Arrival) + lenOfRide // fmt.Printf("%d/%d\n", lenOfRide, total) if bestRide == nil || lenOfRide*bestTotal > total*bestLenOfRide { bestLenOfRide = lenOfRide bestTotal = total bestRide = r } } // if bestRide != nil { // fmt.Printf("Picking %d %d -> %d %d\n", bestRide.a, bestRide.b, bestRide.x, bestRide.y) // } return bestRide } func assign() bool { c := Sched.Pop() if c == nil { return false } r := Choose(c) if r == nil { return true } r.used = true c.Update(r) Sched.Add(c) return true } func solve() { sort.Sort(ByEndtime(Rides)) Sched = &prioq{} // create cars for i := 0; i < F; i++ { c := &Car{ ID: i, Arrival: 0, X: 0, Y: 0, } Cars = append(Cars, c) Sched.Add(c) } for assign() { } for _, c := range Cars { fmt.Fprintf(output, "%d", len(c.Rides)) for _, ri := range c.Rides { fmt.Fprintf(output, " %d", ri) } fmt.Fprintf(output, "\n") } } func main() { sample := os.Args[1] fileIn := sample + ".in" fileOut := sample + ".out" var err error input, err = os.Open(fileIn) if err != nil { panic(fmt.Sprintf("open %s: %v", fileIn, err)) } output, err = os.Create(fileOut) if err != nil { panic(fmt.Sprintf("creating %s: %v", fileOut, err)) } defer input.Close() defer output.Close() // Global R = readInt() C = readInt() F = readInt() N = readInt() B = readInt() T = readInt() for i := 0; i < N; i++ { Rides = append(Rides, &Ride{ ID: i, a: readInt(), b: readInt(), x: readInt(), y: readInt(), s: readInt(), f: readInt(), }) } solve() } func readInt() int { var i int fmt.Fscanf(input, "%d", &i) return i } func readString() string { var str string fmt.Fscanf(input, "%s", &str) return str } func readFloat() float64 { var x float64 fmt.Fscanf(input, "%f", &x) return x } // Prioq // Invariant: both children are bigger type prioq struct { bintree []*Car } func (pq *prioq) Add(car *Car) { pq.bintree = append(pq.bintree, car) // Rebalance tree to respect invariant var i = len(pq.bintree) - 1 var p = (i - 1) / 2 for p >= 0 && pq.bintree[p].Arrival > pq.bintree[i].Arrival { pq.bintree[p], pq.bintree[i] = pq.bintree[i], pq.bintree[p] i = p p = (i - 1) / 2 } } func (pq *prioq) Pop() *Car { if len(pq.bintree) == 0 { return nil } if len(pq.bintree) == 1 { elem := pq.bintree[0] pq.bintree = pq.bintree[:0] return elem } elem := pq.bintree[0] // Put last element at root pq.bintree[0] = pq.bintree[len(pq.bintree)-1] // Remove last element pq.bintree = pq.bintree[:len(pq.bintree)-1] // 1 9 // 10 9 10 12 // 11 12 13 14 -> 11 12 13 14 // 12 // Rebalance tree to respect invariant len := len(pq.bintree) i, left, right := 0, 0, 0 for { left = 2*i + 1 right = 2*i + 2 if left < len && right < len { // Two children if pq.bintree[left].Arrival <= pq.bintree[right].Arrival { if pq.bintree[i].Arrival <= pq.bintree[left].Arrival { break // Inferior to both children } else { pq.bintree[i], pq.bintree[left] = pq.bintree[left], pq.bintree[i] i = left } } else { if pq.bintree[i].Arrival <= pq.bintree[right].Arrival { break // Inferior to both children } else { pq.bintree[i], pq.bintree[right] = pq.bintree[right], pq.bintree[i] i = right } } } else if left < len { // One child (left) if pq.bintree[i].Arrival <= pq.bintree[left].Arrival { break // Inferior to only child } pq.bintree[i], pq.bintree[left] = pq.bintree[left], pq.bintree[i] i = left } else { // No child break } } return elem } func (pq *prioq) empty() bool { return len(pq.bintree) == 0 }