main.go 4.7 KB

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