main.go 6.2 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375
  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 || (rs[i].f == rs[j].f && rs[i].length() < rs[j].length())
  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. score int
  61. }
  62. func (c *Car) Update(r *Ride) {
  63. c.moveTo(r.a, r.b)
  64. if c.Arrival <= r.s {
  65. c.Arrival = r.s
  66. // count bonus points for being on time
  67. c.score += B
  68. }
  69. c.moveTo(r.x, r.y)
  70. c.score += r.length()
  71. c.Rides = append(c.Rides, r.ID)
  72. }
  73. func (c *Car) EarliestFinish(r *Ride) int {
  74. copy := &Car{
  75. Arrival: c.Arrival,
  76. X: c.X,
  77. Y: c.Y,
  78. }
  79. copy.moveTo(r.a, r.b)
  80. if copy.Arrival < r.s {
  81. copy.Arrival = r.s
  82. }
  83. copy.moveTo(r.x, r.y)
  84. return copy.Arrival
  85. }
  86. func (c *Car) moveTo(x, y int) {
  87. xdist := c.X - x
  88. if xdist < 0 {
  89. xdist = -xdist
  90. }
  91. ydist := c.Y - y
  92. if ydist < 0 {
  93. ydist = -ydist
  94. }
  95. c.Arrival += xdist + ydist
  96. c.X = x
  97. c.Y = y
  98. }
  99. func (c *Car) distanceTo(x, y int) int {
  100. return abs(c.X-x) + abs(c.Y-y)
  101. }
  102. func max(a, b int) int {
  103. if a > b {
  104. return a
  105. } else {
  106. return b
  107. }
  108. }
  109. func (c *Car) CanPick(r *Ride) bool {
  110. return !r.used && r.f >= c.EarliestFinish(r)
  111. }
  112. func (c *Car) pickClosestLate() *Ride {
  113. var best *Ride
  114. var dbest = 999999999
  115. for _, r := range Rides {
  116. if !c.CanPick(r) {
  117. continue
  118. }
  119. d := c.distanceTo(r.a, r.b)
  120. if d < dbest && d > r.s-c.Arrival {
  121. best = r
  122. dbest = d
  123. }
  124. }
  125. return best
  126. }
  127. func Choose(c *Car) *Ride {
  128. var bestRide *Ride
  129. bestLenOfRide := 0
  130. bestTotal := 0
  131. // fmt.Printf("car %d\n", c.ID)
  132. for _, r := range Rides {
  133. if !c.CanPick(r) {
  134. continue
  135. }
  136. // fmt.Printf("%d %d -> %d %d\n", r.a, r.b, r.x, r.y)
  137. lenOfRide := r.length()
  138. total := max(c.distanceTo(r.a, r.b), r.s-c.Arrival) + lenOfRide
  139. // fmt.Printf("%d/%d\n", lenOfRide, total)
  140. if bestRide == nil || lenOfRide*bestTotal > 90*total*bestLenOfRide {
  141. bestLenOfRide = lenOfRide
  142. bestTotal = total
  143. bestRide = r
  144. }
  145. }
  146. // if bestRide != nil {
  147. // fmt.Printf("Picking %d %d -> %d %d\n", bestRide.a, bestRide.b, bestRide.x, bestRide.y)
  148. // }
  149. if bestRide != nil {
  150. r := c.pickClosestLate()
  151. if r != nil {
  152. bestRide = r
  153. }
  154. }
  155. return bestRide
  156. }
  157. func assign() bool {
  158. c := Sched.Pop()
  159. if c == nil {
  160. return false
  161. }
  162. r := Choose(c)
  163. if r == nil {
  164. return true
  165. }
  166. r.used = true
  167. c.Update(r)
  168. Sched.Add(c)
  169. return true
  170. }
  171. func solve() {
  172. sort.Sort(ByEndtime(Rides))
  173. Sched = &prioq{}
  174. // create cars
  175. for i := 0; i < F; i++ {
  176. c := &Car{
  177. ID: i,
  178. Arrival: 0,
  179. X: 0,
  180. Y: 0,
  181. }
  182. Cars = append(Cars, c)
  183. Sched.Add(c)
  184. }
  185. for assign() {
  186. }
  187. totalScore := 0
  188. for _, c := range Cars {
  189. fmt.Fprintf(output, "%d", len(c.Rides))
  190. for _, ri := range c.Rides {
  191. fmt.Fprintf(output, " %d", ri)
  192. }
  193. fmt.Fprintf(output, "\n")
  194. totalScore += c.score
  195. }
  196. fmt.Printf("%d\n", totalScore)
  197. }
  198. func main() {
  199. sample := os.Args[1]
  200. fileIn := sample + ".in"
  201. fileOut := sample + ".out"
  202. var err error
  203. input, err = os.Open(fileIn)
  204. if err != nil {
  205. panic(fmt.Sprintf("open %s: %v", fileIn, err))
  206. }
  207. output, err = os.Create(fileOut)
  208. if err != nil {
  209. panic(fmt.Sprintf("creating %s: %v", fileOut, err))
  210. }
  211. defer input.Close()
  212. defer output.Close()
  213. // Global
  214. R = readInt()
  215. C = readInt()
  216. F = readInt()
  217. N = readInt()
  218. B = readInt()
  219. T = readInt()
  220. for i := 0; i < N; i++ {
  221. Rides = append(Rides, &Ride{
  222. ID: i,
  223. a: readInt(),
  224. b: readInt(),
  225. x: readInt(),
  226. y: readInt(),
  227. s: readInt(),
  228. f: readInt(),
  229. })
  230. }
  231. solve()
  232. }
  233. func readInt() int {
  234. var i int
  235. fmt.Fscanf(input, "%d", &i)
  236. return i
  237. }
  238. func readString() string {
  239. var str string
  240. fmt.Fscanf(input, "%s", &str)
  241. return str
  242. }
  243. func readFloat() float64 {
  244. var x float64
  245. fmt.Fscanf(input, "%f", &x)
  246. return x
  247. }
  248. // Prioq
  249. // Invariant: both children are bigger
  250. type prioq struct {
  251. bintree []*Car
  252. }
  253. func (pq *prioq) Add(car *Car) {
  254. pq.bintree = append(pq.bintree, car)
  255. // Rebalance tree to respect invariant
  256. var i = len(pq.bintree) - 1
  257. var p = (i - 1) / 2
  258. for p >= 0 && pq.bintree[p].Arrival > pq.bintree[i].Arrival {
  259. pq.bintree[p], pq.bintree[i] = pq.bintree[i], pq.bintree[p]
  260. i = p
  261. p = (i - 1) / 2
  262. }
  263. }
  264. func (pq *prioq) Pop() *Car {
  265. if len(pq.bintree) == 0 {
  266. return nil
  267. }
  268. if len(pq.bintree) == 1 {
  269. elem := pq.bintree[0]
  270. pq.bintree = pq.bintree[:0]
  271. return elem
  272. }
  273. elem := pq.bintree[0]
  274. // Put last element at root
  275. pq.bintree[0] = pq.bintree[len(pq.bintree)-1]
  276. // Remove last element
  277. pq.bintree = pq.bintree[:len(pq.bintree)-1]
  278. // 1 9
  279. // 10 9 10 12
  280. // 11 12 13 14 -> 11 12 13 14
  281. // 12
  282. // Rebalance tree to respect invariant
  283. len := len(pq.bintree)
  284. i, left, right := 0, 0, 0
  285. for {
  286. left = 2*i + 1
  287. right = 2*i + 2
  288. if left < len && right < len { // Two children
  289. if pq.bintree[left].Arrival <= pq.bintree[right].Arrival {
  290. if pq.bintree[i].Arrival <= pq.bintree[left].Arrival {
  291. break // Inferior to both children
  292. } else {
  293. pq.bintree[i], pq.bintree[left] = pq.bintree[left], pq.bintree[i]
  294. i = left
  295. }
  296. } else {
  297. if pq.bintree[i].Arrival <= pq.bintree[right].Arrival {
  298. break // Inferior to both children
  299. } else {
  300. pq.bintree[i], pq.bintree[right] = pq.bintree[right], pq.bintree[i]
  301. i = right
  302. }
  303. }
  304. } else if left < len { // One child (left)
  305. if pq.bintree[i].Arrival <= pq.bintree[left].Arrival {
  306. break // Inferior to only child
  307. }
  308. pq.bintree[i], pq.bintree[left] = pq.bintree[left], pq.bintree[i]
  309. i = left
  310. } else { // No child
  311. break
  312. }
  313. }
  314. return elem
  315. }
  316. func (pq *prioq) empty() bool {
  317. return len(pq.bintree) == 0
  318. }