main.go 4.1 KB

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