main.go 5.2 KB

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