Submission #27971957

---

Source Code Expand

import std.algorithm, std.array, std.container, std.conv, std.math, std.numeric, std.random, std.range, std.stdio, std.string, std.typecons, core.bitop;

struct Point { int x, y; };

struct Route { int id; Point from, to; };

int mhdistance(Point a, Point b)
{
  return abs(a.x - b.x) + abs(a.y - b.y);
}

double distance(Point a, Point b)
{
  return mhdistance(a, b);
}

double route_score(Point base, Route r)
{
  double d1 = distance(base, r.from), d2 = distance(base, r.to);
  return d1 * d1 + d2 * d2;
}

long solve(Route[] pending_routes, ref int[] done_routes, ref int[] ans)
{
  int m = 50;
  Point[] pending_dest;
  Point lastpos = Point(400, 400);

  ans ~= 400;
  ans ~= 400;

  long score = 0;

  while (done_routes.length < m || pending_dest.length > 0) {
    bool do_route = false;
    if (pending_dest.length == 0) {
      do_route = true;
    } else if (done_routes.length < m) {
      if (distance(pending_routes[0].from, lastpos) <= distance(pending_dest[0], lastpos)) {
        do_route = true;
      }
    }
    if (do_route) {
        score += mhdistance(lastpos, pending_routes[0].from);
        done_routes ~= pending_routes[0].id;
        lastpos = Point(pending_routes[0].from.x, pending_routes[0].from.y);
        ans ~= pending_routes[0].from.x;
        ans ~= pending_routes[0].from.y;
        pending_dest ~= Point(pending_routes[0].to.x, pending_routes[0].to.y);
        pending_routes = pending_routes[1 .. $];
        pending_routes.sort!((a, b) => distance(lastpos, a.from) < distance(lastpos, b.from));
        pending_dest.sort!((a, b) => distance(lastpos, a) < distance(lastpos, b));
    } else {
        score += mhdistance(lastpos, pending_dest[0]);
        lastpos = Point(pending_dest[0].x, pending_dest[0].y);
        ans ~= pending_dest[0].x;
        ans ~= pending_dest[0].y;
        pending_dest = pending_dest[1 .. $];
        pending_dest.sort!((a, b) => distance(lastpos, a) < distance(lastpos, b));
    }
  }

  ans ~= 400;
  ans ~= 400;
  score += mhdistance(lastpos, Point(400, 400));
  return score;
}

void main()
{
  Route[] routes;
  foreach (i ; 0 .. 1000) {
    int x1, y1, x2, y2;
    readf!" %d %d %d %d "(x1, y1, x2, y2);
    routes ~= Route(i + 1, Point(x1, y1), Point(x2, y2));
  }
  auto base = Point(400, 400);
  routes.sort!((a, b) => route_score(base, a) < route_score(base, b));

  int[] final_ans, final_done_routes;
  long best_score = long.max;
  int m = 50;

  foreach (i ; 0 .. 400) {
    int[] ans, done_routes;
    Route[] pending_routes = routes[0 .. m + i].dup;
    long score = solve(pending_routes, done_routes, ans);
    if (score < best_score) {
      final_ans = ans.dup;
      final_done_routes = done_routes.dup;
      best_score = score;
    }
  }

  writefln("%d %s", m, final_done_routes.map!text.join(" "));
  writefln("%d %s", final_ans.length / 2, final_ans.map!text.join(" "));
}

Submission Info

Judge Result