main.go 4.5 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286
  1. package main
  2. import (
  3. "fmt"
  4. "os"
  5. "sort"
  6. )
  7. var input *os.File
  8. var output *os.File
  9. var R int
  10. var C int
  11. var F int
  12. var N int
  13. var B int
  14. var T int
  15. var Rides []*Ride
  16. var Cars []*Car
  17. var Sched Scheduler
  18. type Ride struct {
  19. ID int
  20. a, b, x, y, s, f int
  21. used bool
  22. }
  23. type ByEndtime []*Ride
  24. func (rs ByEndtime) Len() int { return len(rs) }
  25. func (rs ByEndtime) Swap(i, j int) { rs[i], rs[j] = rs[j], rs[i] }
  26. func (rs ByEndtime) Less(i, j int) bool {
  27. return rs[i].f < rs[j].f
  28. }
  29. type Scheduler interface {
  30. Add(*Car)
  31. Pop() *Car
  32. }
  33. type Car struct {
  34. ID int
  35. Rides []int
  36. Arrival int
  37. X int
  38. Y int
  39. }
  40. func (c *Car) Update(r *Ride) {
  41. c.moveTo(r.a, r.b)
  42. c.moveTo(r.x, r.y)
  43. c.Rides = append(c.Rides, r.ID)
  44. }
  45. func (c *Car) EarliestFinish(r *Ride) int {
  46. copy := &Car{
  47. Arrival: c.Arrival,
  48. X: c.X,
  49. Y: c.Y,
  50. }
  51. c.moveTo(r.a, r.b)
  52. c.moveTo(r.x, r.y)
  53. return copy.Arrival
  54. }
  55. func (c *Car) moveTo(x, y int) {
  56. xdist := c.X - x
  57. if xdist < 0 {
  58. xdist = -xdist
  59. }
  60. ydist := c.Y - y
  61. if ydist < 0 {
  62. ydist = -ydist
  63. }
  64. c.Arrival += xdist + ydist
  65. c.X = x
  66. c.Y = y
  67. }
  68. func Choose(c *Car) *Ride {
  69. for _, r := range Rides {
  70. if r.used {
  71. continue
  72. }
  73. if r.f < c.EarliestFinish(r) {
  74. continue
  75. }
  76. return r
  77. }
  78. return nil
  79. }
  80. func assign() bool {
  81. c := Sched.Pop()
  82. if c == nil {
  83. return false
  84. }
  85. r := Choose(c)
  86. if r == nil {
  87. return true
  88. }
  89. r.used = true
  90. c.Update(r)
  91. Sched.Add(c)
  92. return true
  93. }
  94. func solve() {
  95. sort.Sort(ByEndtime(Rides))
  96. Sched = &prioq{}
  97. // create cars
  98. for i := 0; i < F; i++ {
  99. c := &Car{
  100. ID: i,
  101. Arrival: 0,
  102. X: 0,
  103. Y: 0,
  104. }
  105. Cars = append(Cars, c)
  106. Sched.Add(c)
  107. }
  108. for assign() {
  109. }
  110. for _, c := range Cars {
  111. fmt.Fprintf(output, "%d", len(c.Rides))
  112. for _, ri := range c.Rides {
  113. fmt.Fprintf(output, " %d", ri)
  114. }
  115. fmt.Fprintf(output, "\n")
  116. }
  117. }
  118. func main() {
  119. sample := os.Args[1]
  120. fileIn := sample + ".in"
  121. fileOut := sample + ".out"
  122. var err error
  123. input, err = os.Open(fileIn)
  124. if err != nil {
  125. panic(fmt.Sprintf("open %s: %v", fileIn, err))
  126. }
  127. output, err = os.Create(fileOut)
  128. if err != nil {
  129. panic(fmt.Sprintf("creating %s: %v", fileOut, err))
  130. }
  131. defer input.Close()
  132. defer output.Close()
  133. // Global
  134. R = readInt()
  135. C = readInt()
  136. F = readInt()
  137. N = readInt()
  138. B = readInt()
  139. T = readInt()
  140. for i := 0; i < N; i++ {
  141. Rides = append(Rides, &Ride{
  142. ID: i,
  143. a: readInt(),
  144. b: readInt(),
  145. x: readInt(),
  146. y: readInt(),
  147. s: readInt(),
  148. f: readInt(),
  149. })
  150. }
  151. solve()
  152. }
  153. func readInt() int {
  154. var i int
  155. fmt.Fscanf(input, "%d", &i)
  156. return i
  157. }
  158. func readString() string {
  159. var str string
  160. fmt.Fscanf(input, "%s", &str)
  161. return str
  162. }
  163. func readFloat() float64 {
  164. var x float64
  165. fmt.Fscanf(input, "%f", &x)
  166. return x
  167. }
  168. // Prioq
  169. // Invariant: both children are bigger
  170. type prioq struct {
  171. bintree []*Car
  172. }
  173. func (pq *prioq) Add(car *Car) {
  174. pq.bintree = append(pq.bintree, car)
  175. // Rebalance tree to respect invariant
  176. var i = len(pq.bintree) - 1
  177. var p = (i - 1) / 2
  178. for p >= 0 && pq.bintree[p].Arrival > pq.bintree[i].Arrival {
  179. pq.bintree[p], pq.bintree[i] = pq.bintree[i], pq.bintree[p]
  180. i = p
  181. p = (i - 1) / 2
  182. }
  183. }
  184. func (pq *prioq) Pop() *Car {
  185. if len(pq.bintree) == 0 {
  186. return nil
  187. }
  188. if len(pq.bintree) == 1 {
  189. elem := pq.bintree[0]
  190. pq.bintree = pq.bintree[:0]
  191. return elem
  192. }
  193. elem := pq.bintree[0]
  194. // Put last element at root
  195. pq.bintree[0] = pq.bintree[len(pq.bintree)-1]
  196. // Remove last element
  197. pq.bintree = pq.bintree[:len(pq.bintree)-1]
  198. // 1 9
  199. // 10 9 10 12
  200. // 11 12 13 14 -> 11 12 13 14
  201. // 12
  202. // Rebalance tree to respect invariant
  203. len := len(pq.bintree)
  204. i, left, right := 0, 0, 0
  205. for {
  206. left = 2*i + 1
  207. right = 2*i + 2
  208. if left < len && right < len { // Two children
  209. if pq.bintree[left].Arrival <= pq.bintree[right].Arrival {
  210. if pq.bintree[i].Arrival <= pq.bintree[left].Arrival {
  211. break // Inferior to both children
  212. } else {
  213. pq.bintree[i], pq.bintree[left] = pq.bintree[left], pq.bintree[i]
  214. i = left
  215. }
  216. } else {
  217. if pq.bintree[i].Arrival <= pq.bintree[right].Arrival {
  218. break // Inferior to both children
  219. } else {
  220. pq.bintree[i], pq.bintree[right] = pq.bintree[right], pq.bintree[i]
  221. i = right
  222. }
  223. }
  224. } else if left < len { // One child (left)
  225. if pq.bintree[i].Arrival <= pq.bintree[left].Arrival {
  226. break // Inferior to only child
  227. }
  228. pq.bintree[i], pq.bintree[left] = pq.bintree[left], pq.bintree[i]
  229. i = left
  230. } else { // No child
  231. break
  232. }
  233. }
  234. return elem
  235. }
  236. func (pq *prioq) empty() bool {
  237. return len(pq.bintree) == 0
  238. }