Submission #71292466

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

static long long L_global;
static int T_global;

struct Point {
  double x;
  double y;
  double vx;
  double vy;
};

// Get position of point at time t
Point get_pos_at_time(const Point &p, int t) {
  Point result;
  result.x = fmod(p.x + p.vx * t, (double)L_global);
  result.y = fmod(p.y + p.vy * t, (double)L_global);
  if (result.x < 0)
    result.x += L_global;
  if (result.y < 0)
    result.y += L_global;
  result.vx = p.vx;
  result.vy = p.vy;
  return result;
}

// Torus distance between two points
double torus_dist(const Point &a, const Point &b) {
  double dx = abs(a.x - b.x);
  double dy = abs(a.y - b.y);
  dx = min(dx, L_global - dx);
  dy = min(dy, L_global - dy);
  return sqrt(dx * dx + dy * dy);
}

// Calculate total merge cost for a grouping (all merges at t=0)
long long calc_cost(const vector<vector<int>> &groups,
                    const vector<Point> &pts) {
  long long total = 0;
  for (const auto &g : groups) {
    if (g.size() <= 1)
      continue;
    // Use MST-like approach: connect each node to closest already-connected
    // node
    vector<bool> in_tree(g.size(), false);
    in_tree[0] = true;
    int in_count = 1;
    while (in_count < (int)g.size()) {
      double best_d = 1e18;
      int best_j = -1;
      for (int i = 0; i < (int)g.size(); ++i) {
        if (in_tree[i])
          continue;
        for (int j = 0; j < (int)g.size(); ++j) {
          if (!in_tree[j])
            continue;
          double d = torus_dist(pts[g[i]], pts[g[j]]);
          if (d < best_d) {
            best_d = d;
            best_j = i;
          }
        }
      }
      if (best_j >= 0) {
        in_tree[best_j] = true;
        ++in_count;
        total += (long long)round(best_d);
      }
    }
  }
  return total;
}

// Find the time t in [0, T) that minimizes distance between two points
// considering their velocities and torus wrapping
pair<int, double> find_best_merge_time(double x1, double y1, double vx1,
                                       double vy1, double x2, double y2,
                                       double vx2, double vy2, int T) {
  int best_t = 0;
  double best_dist = 1e18;

  // Check every time step (could optimize with math, but this is simple)
  for (int t = 0; t < T; ++t) {
    double px1 = fmod(x1 + vx1 * t, (double)L_global);
    double py1 = fmod(y1 + vy1 * t, (double)L_global);
    double px2 = fmod(x2 + vx2 * t, (double)L_global);
    double py2 = fmod(y2 + vy2 * t, (double)L_global);
    if (px1 < 0)
      px1 += L_global;
    if (py1 < 0)
      py1 += L_global;
    if (px2 < 0)
      px2 += L_global;
    if (py2 < 0)
      py2 += L_global;

    double dx = abs(px1 - px2);
    double dy = abs(py1 - py2);
    dx = min(dx, L_global - dx);
    dy = min(dy, L_global - dy);
    double d = sqrt(dx * dx + dy * dy);

    if (d < best_dist) {
      best_dist = d;
      best_t = t;
    }
  }

  return {best_t, best_dist};
}

// For each pair of points, precompute the best merge time
vector<tuple<int, double, int, int>>
precompute_best_times(const vector<int> &group, const vector<Point> &pts,
                      int T) {
  vector<tuple<int, double, int, int>> result; // (best_t, best_dist, i, j)

  int sz = group.size();
  for (int i = 0; i < sz; ++i) {
    for (int j = i + 1; j < sz; ++j) {
      double x1 = pts[group[i]].x, y1 = pts[group[i]].y;
      double vx1 = pts[group[i]].vx, vy1 = pts[group[i]].vy;
      double x2 = pts[group[j]].x, y2 = pts[group[j]].y;
      double vx2 = pts[group[j]].vx, vy2 = pts[group[j]].vy;

      int best_t = 0;
      double best_dist = 1e18;

      for (int t = 0; t < T; ++t) {
        double px1 = fmod(x1 + vx1 * t, (double)L_global);
        double py1 = fmod(y1 + vy1 * t, (double)L_global);
        double px2 = fmod(x2 + vx2 * t, (double)L_global);
        double py2 = fmod(y2 + vy2 * t, (double)L_global);
        if (px1 < 0)
          px1 += L_global;
        if (py1 < 0)
          py1 += L_global;
        if (px2 < 0)
          px2 += L_global;
        if (py2 < 0)
          py2 += L_global;

        double dx = abs(px1 - px2);
        double dy = abs(py1 - py2);
        dx = min(dx, L_global - dx);
        dy = min(dy, L_global - dy);
        double d = sqrt(dx * dx + dy * dy);

        if (d < best_dist) {
          best_dist = d;
          best_t = t;
        }
      }
      result.emplace_back(best_t, best_dist, i, j);
    }
  }

  // Sort by best distance (smallest first)
  sort(result.begin(), result.end(),
       [](const auto &a, const auto &b) { return get<1>(a) < get<1>(b); });

  return result;
}

// Generate ops from groups using simulation-based greedy approach
// that properly accounts for velocity changes after merges
vector<tuple<int, int, int>> make_ops_greedy(const vector<vector<int>> &groups,
                                             const vector<Point> &pts,
                                             int limit, int T) {
  vector<tuple<int, int, int>> all_ops;

  // Process each group independently
  for (int gidx = 0; gidx < (int)groups.size(); ++gidx) {
    const auto &group = groups[gidx];
    int sz = group.size();
    if (sz <= 1)
      continue;

    // DSU for this group
    vector<int> parent(sz), comp_size(sz, 1);
    vector<double> comp_vx(sz), comp_vy(sz);
    vector<double> pos_x(sz), pos_y(sz);
    iota(parent.begin(), parent.end(), 0);
    for (int i = 0; i < sz; ++i) {
      comp_vx[i] = pts[group[i]].vx;
      comp_vy[i] = pts[group[i]].vy;
      pos_x[i] = pts[group[i]].x;
      pos_y[i] = pts[group[i]].y;
    }

    // Non-recursive find with path compression
    auto find = [&](int i) -> int {
      int root = i;
      while (parent[root] != root)
        root = parent[root];
      while (parent[i] != root) {
        int next = parent[i];
        parent[i] = root;
        i = next;
      }
      return root;
    };

    auto unite = [&](int i, int j) {
      int ri = find(i);
      int rj = find(j);
      if (ri == rj)
        return;
      if (comp_size[ri] < comp_size[rj])
        swap(ri, rj);
      int si = comp_size[ri];
      int sj = comp_size[rj];
      double new_vx = (si * comp_vx[ri] + sj * comp_vx[rj]) / (si + sj);
      double new_vy = (si * comp_vy[ri] + sj * comp_vy[rj]) / (si + sj);
      parent[rj] = ri;
      comp_size[ri] += comp_size[rj];
      comp_vx[ri] = new_vx;
      comp_vy[ri] = new_vy;
    };

    auto step = [&]() {
      for (int i = 0; i < sz; ++i) {
        int r = find(i);
        pos_x[i] = fmod(pos_x[i] + comp_vx[r], (double)L_global);
        pos_y[i] = fmod(pos_y[i] + comp_vy[r], (double)L_global);
        if (pos_x[i] < 0)
          pos_x[i] += L_global;
        if (pos_y[i] < 0)
          pos_y[i] += L_global;
      }
    };

    auto get_dist = [&](int i, int j) {
      double dx = abs(pos_x[i] - pos_x[j]);
      double dy = abs(pos_y[i] - pos_y[j]);
      dx = min(dx, L_global - dx);
      dy = min(dy, L_global - dy);
      return sqrt(dx * dx + dy * dy);
    };

    // Lightweight lookahead: only check best pair
    auto find_min_dist_in_future = [&](int i, int j, int lookahead) {
      double min_d = 1e18;
      int ri = find(i);
      int rj = find(j);
      double vxi = comp_vx[ri], vyi = comp_vy[ri];
      double vxj = comp_vx[rj], vyj = comp_vy[rj];

      for (int dt = 0; dt < lookahead; ++dt) {
        double pxi = fmod(pos_x[i] + vxi * dt, (double)L_global);
        double pyi = fmod(pos_y[i] + vyi * dt, (double)L_global);
        double pxj = fmod(pos_x[j] + vxj * dt, (double)L_global);
        double pyj = fmod(pos_y[j] + vyj * dt, (double)L_global);
        if (pxi < 0)
          pxi += L_global;
        if (pyi < 0)
          pyi += L_global;
        if (pxj < 0)
          pxj += L_global;
        if (pyj < 0)
          pyj += L_global;

        double dx = abs(pxi - pxj);
        double dy = abs(pyi - pyj);
        dx = min(dx, L_global - dx);
        dy = min(dy, L_global - dy);
        min_d = min(min_d, sqrt(dx * dx + dy * dy));
      }
      return min_d;
    };

    int remaining_merges = sz - 1;
    vector<tuple<int, int, int>> group_ops;
    const int LOOKAHEAD = 100;

    for (int t = 0; t < T && remaining_merges > 0; ++t) {
      int time_left = T - t;

      // Find the closest pair from different components
      double best_d = 1e18;
      int best_i = -1, best_j = -1;

      for (int i = 0; i < sz; ++i) {
        for (int j = i + 1; j < sz; ++j) {
          if (find(i) == find(j))
            continue;
          double d = get_dist(i, j);
          if (d < best_d) {
            best_d = d;
            best_i = i;
            best_j = j;
          }
        }
      }

      if (best_i < 0)
        break;

      // Check if waiting might give better distance
      double future_d = find_min_dist_in_future(best_i, best_j, LOOKAHEAD);

      bool should_merge = false;

      // Merge if current distance is close to future optimal
      if (best_d <= future_d * 1.1) {
        should_merge = true;
      }
      // Merge if distance is small enough
      if (best_d < 500.0) {
        should_merge = true;
      }
      // Merge if running out of time
      if (time_left <= remaining_merges + 5) {
        should_merge = true;
      }

      if (should_merge) {
        group_ops.emplace_back(t, group[best_i], group[best_j]);
        unite(best_i, best_j);
        remaining_merges--;
      }

      step();
    }

    // Force remaining merges if needed
    while (remaining_merges > 0) {
      double best_d = 1e18;
      int best_i = -1, best_j = -1;
      for (int i = 0; i < sz; ++i) {
        for (int j = i + 1; j < sz; ++j) {
          if (find(i) == find(j))
            continue;
          double d = get_dist(i, j);
          if (d < best_d) {
            best_d = d;
            best_i = i;
            best_j = j;
          }
        }
      }
      if (best_i >= 0) {
        group_ops.emplace_back(T - 1, group[best_i], group[best_j]);
        unite(best_i, best_j);
        remaining_merges--;
      } else {
        break;
      }
    }

    for (auto &op : group_ops) {
      all_ops.push_back(op);
    }
  }

  return all_ops;
}

// Generate ops from groups using MST order (fallback)
vector<tuple<int, int, int>> make_ops(const vector<vector<int>> &groups,
                                      const vector<Point> &pts, int limit) {
  vector<tuple<int, int, int>> ops;
  ops.reserve(limit);
  for (const auto &g : groups) {
    if (g.size() <= 1)
      continue;
    vector<bool> in_tree(g.size(), false);
    in_tree[0] = true;
    int in_count = 1;
    while (in_count < (int)g.size() && (int)ops.size() < limit) {
      double best_d = 1e18;
      int best_i = -1, best_j = -1;
      for (int i = 0; i < (int)g.size(); ++i) {
        if (in_tree[i])
          continue;
        for (int j = 0; j < (int)g.size(); ++j) {
          if (!in_tree[j])
            continue;
          double d = torus_dist(pts[g[i]], pts[g[j]]);
          if (d < best_d) {
            best_d = d;
            best_i = i;
            best_j = j;
          }
        }
      }
      if (best_i >= 0) {
        in_tree[best_i] = true;
        ++in_count;
        ops.emplace_back(0, g[best_j], g[best_i]);
      }
    }
  }
  return ops;
}

// 操作列から実際の結合コストを計算（シミュレーション）
long long calc_ops_cost(const vector<tuple<int, int, int>> &ops,
                        const vector<Point> &pts, int N, int T, long long L) {
  vector<int> parent(N), comp_size(N, 1);
  vector<double> comp_vx(N), comp_vy(N);
  vector<double> pos_x(N), pos_y(N);
  iota(parent.begin(), parent.end(), 0);
  for (int j = 0; j < N; ++j) {
    comp_vx[j] = pts[j].vx;
    comp_vy[j] = pts[j].vy;
    pos_x[j] = pts[j].x;
    pos_y[j] = pts[j].y;
  }

  // Non-recursive find with path compression
  auto find = [&](int i) -> int {
    int root = i;
    while (parent[root] != root)
      root = parent[root];
    while (parent[i] != root) {
      int next = parent[i];
      parent[i] = root;
      i = next;
    }
    return root;
  };

  // opsを時刻順にソート
  vector<tuple<int, int, int>> sorted_ops = ops;
  sort(sorted_ops.begin(), sorted_ops.end());

  long long total_cost = 0;
  int op_idx = 0;
  for (int t = 0; t < T && op_idx < (int)sorted_ops.size(); ++t) {
    // 時刻tでの結合を処理
    while (op_idx < (int)sorted_ops.size() && get<0>(sorted_ops[op_idx]) == t) {
      int pi = get<1>(sorted_ops[op_idx]);
      int pj = get<2>(sorted_ops[op_idx]);

      // 距離計算
      double dx = abs(pos_x[pi] - pos_x[pj]);
      double dy = abs(pos_y[pi] - pos_y[pj]);
      dx = min(dx, L - dx);
      dy = min(dy, L - dy);
      total_cost += (long long)round(sqrt(dx * dx + dy * dy));

      // 結合
      int ri = find(pi);
      int rj = find(pj);
      if (ri != rj) {
        if (comp_size[ri] < comp_size[rj])
          swap(ri, rj);
        int si = comp_size[ri];
        int sj = comp_size[rj];
        double new_vx = (si * comp_vx[ri] + sj * comp_vx[rj]) / (si + sj);
        double new_vy = (si * comp_vy[ri] + sj * comp_vy[rj]) / (si + sj);
        parent[rj] = ri;
        comp_size[ri] += comp_size[rj];
        comp_vx[ri] = new_vx;
        comp_vy[ri] = new_vy;
      }
      ++op_idx;
    }

    // 移動
    for (int j = 0; j < N; ++j) {
      int r = find(j);
      pos_x[j] = fmod(pos_x[j] + comp_vx[r], (double)L);
      pos_y[j] = fmod(pos_y[j] + comp_vy[r], (double)L);
      if (pos_x[j] < 0)
        pos_x[j] += L;
      if (pos_y[j] < 0)
        pos_y[j] += L;
    }
  }

  return total_cost;
}

// k-means++ style initialization on torus with random time offsets
vector<vector<int>> kmeans_grouping(const vector<Point> &pts, int m, int k,
                                    mt19937 &rng) {
  int n = (int)pts.size();

  // Generate random time for each point
  vector<int> rand_time(n);
  for (int i = 0; i < n; ++i) {
    rand_time[i] = rng() % T_global;
  }

  // Compute positions at random times
  vector<Point> rand_pts(n);
  for (int i = 0; i < n; ++i) {
    rand_pts[i] = get_pos_at_time(pts[i], rand_time[i]);
  }

  vector<int> centers;
  centers.reserve(m);

  // Pick first center randomly
  centers.push_back(rng() % n);

  // Pick remaining centers with probability proportional to distance^2
  for (int c = 1; c < m; ++c) {
    vector<double> min_dist(n, 1e18);
    for (int i = 0; i < n; ++i) {
      for (int cid : centers) {
        min_dist[i] = min(min_dist[i], torus_dist(rand_pts[i], rand_pts[cid]));
      }
    }
    vector<double> weights(n);
    for (int i = 0; i < n; ++i) {
      weights[i] = min_dist[i] * min_dist[i];
    }
    discrete_distribution<int> dist(weights.begin(), weights.end());
    centers.push_back(dist(rng));
  }

  // Assign each point to nearest center, but limit group size to k
  vector<pair<double, int>> assignments(n); // (distance, point_id)
  for (int i = 0; i < n; ++i) {
    double best_d = 1e18;
    for (int cid : centers) {
      best_d = min(best_d, torus_dist(rand_pts[i], rand_pts[cid]));
    }
    assignments[i] = {best_d, i};
  }

  // Greedy assignment: closest points first
  sort(assignments.begin(), assignments.end());

  vector<vector<int>> groups(m);
  vector<int> group_size(m, 0);

  for (auto &[d, pid] : assignments) {
    double best_d = 1e18;
    int best_g = -1;
    for (int g = 0; g < m; ++g) {
      if (group_size[g] >= k)
        continue;
      double dist = torus_dist(rand_pts[pid], rand_pts[centers[g]]);
      if (dist < best_d) {
        best_d = dist;
        best_g = g;
      }
    }
    if (best_g >= 0) {
      groups[best_g].push_back(pid);
      group_size[best_g]++;
    }
  }

  return groups;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  // 時間計測を最初から開始
  auto start_time = chrono::steady_clock::now();
#ifdef ONLINE_JUDGE
  const double TIME_LIMIT = 1.9; // seconds (for judge)
#else
  const double TIME_LIMIT = 0.95; // seconds (for local)
#endif

  auto get_elapsed = [&]() {
    return chrono::duration<double>(chrono::steady_clock::now() - start_time)
        .count();
  };

  int N, T, M, K;
  long long L;
  if (!(cin >> N >> T >> M >> K >> L)) {
    return 0;
  }
  L_global = L;
  T_global = T;

  vector<Point> points(N);
  for (int i = 0; i < N; ++i) {
    cin >> points[i].x >> points[i].y >> points[i].vx >> points[i].vy;
  }

  mt19937 rng(42);
  const int NUM_TRIALS = 200;
  const int TOP_K = 3; // 上位いくつの初期解に対して結合を試すか

  // 全ての初期解とそのコストを保存
  vector<pair<long long, vector<vector<int>>>> all_groups;
  all_groups.reserve(NUM_TRIALS);

  for (int trial = 0; trial < NUM_TRIALS; ++trial) {
    vector<vector<int>> groups = kmeans_grouping(points, M, K, rng);
    long long cost = calc_cost(groups, points);
    all_groups.emplace_back(cost, std::move(groups));
  }

  // コストでソートして上位TOP_K個を取得
  sort(all_groups.begin(), all_groups.end());

  // 上位TOP_K個の初期解に対して結合操作を試す
  vector<tuple<int, int, int>> best_ops;
  long long best_total_cost = LLONG_MAX;
  vector<vector<int>> best_groups;

  int num_to_try = min(TOP_K, (int)all_groups.size());
  for (int i = 0; i < num_to_try; ++i) {
    const auto &groups = all_groups[i].second;
    auto ops = make_ops_greedy(groups, points, N - M, T);

    long long total_cost = calc_ops_cost(ops, points, N, T, L);

    if (total_cost < best_total_cost) {
      best_total_cost = total_cost;
      best_ops = ops;
      best_groups = groups;
    }
  }

  // 遠距離結合の見直し処理: グループ間で点をスワップして改善を試みる
  while (true) {
    if (get_elapsed() > TIME_LIMIT)
      break;
    // 各結合操作のコストを計算し、高コスト結合に関わる点を特定
    vector<tuple<long long, int, int, int>> op_costs; // (cost, t, pi, pj)
    {
      vector<int> parent(N), comp_size(N, 1);
      vector<double> comp_vx(N), comp_vy(N);
      vector<double> pos_x(N), pos_y(N);
      iota(parent.begin(), parent.end(), 0);
      for (int j = 0; j < N; ++j) {
        comp_vx[j] = points[j].vx;
        comp_vy[j] = points[j].vy;
        pos_x[j] = points[j].x;
        pos_y[j] = points[j].y;
      }

      // Non-recursive find with path compression
      auto find = [&](int i) -> int {
        int root = i;
        while (parent[root] != root)
          root = parent[root];
        while (parent[i] != root) {
          int next = parent[i];
          parent[i] = root;
          i = next;
        }
        return root;
      };

      vector<tuple<int, int, int>> sorted_ops = best_ops;
      sort(sorted_ops.begin(), sorted_ops.end());

      int op_idx = 0;
      for (int t = 0; t < T && op_idx < (int)sorted_ops.size(); ++t) {
        while (op_idx < (int)sorted_ops.size() &&
               get<0>(sorted_ops[op_idx]) == t) {
          int pi = get<1>(sorted_ops[op_idx]);
          int pj = get<2>(sorted_ops[op_idx]);

          double dx = abs(pos_x[pi] - pos_x[pj]);
          double dy = abs(pos_y[pi] - pos_y[pj]);
          dx = min(dx, (double)L - dx);
          dy = min(dy, (double)L - dy);
          long long cost = (long long)round(sqrt(dx * dx + dy * dy));

          op_costs.emplace_back(cost, t, pi, pj);

          int ri = find(pi);
          int rj = find(pj);
          if (ri != rj) {
            if (comp_size[ri] < comp_size[rj])
              swap(ri, rj);
            int si = comp_size[ri];
            int sj = comp_size[rj];
            double new_vx = (si * comp_vx[ri] + sj * comp_vx[rj]) / (si + sj);
            double new_vy = (si * comp_vy[ri] + sj * comp_vy[rj]) / (si + sj);
            parent[rj] = ri;
            comp_size[ri] += comp_size[rj];
            comp_vx[ri] = new_vx;
            comp_vy[ri] = new_vy;
          }
          ++op_idx;
        }

        for (int j = 0; j < N; ++j) {
          int r = find(j);
          pos_x[j] = fmod(pos_x[j] + comp_vx[r], (double)L);
          pos_y[j] = fmod(pos_y[j] + comp_vy[r], (double)L);
          if (pos_x[j] < 0)
            pos_x[j] += L;
          if (pos_y[j] < 0)
            pos_y[j] += L;
        }
      }
    }

    // コストが高い順にソート
    sort(op_costs.begin(), op_costs.end(),
         [](const auto &a, const auto &b) { return get<0>(a) > get<0>(b); });

    // 各点がどのグループに属するか
    vector<int> point_to_group(N, -1);
    for (int g = 0; g < M; ++g) {
      for (int pid : best_groups[g]) {
        point_to_group[pid] = g;
      }
    }

    // 上位の高コスト結合について、点のグループ間スワップを試みる
    bool improved = false;
    int num_to_check = min(30, (int)op_costs.size());

    for (int c = 0; c < num_to_check && !improved; ++c) {
      // 時間チェック
      if (get_elapsed() > TIME_LIMIT)
        break;

      auto [cost, t_op, pi, pj] = op_costs[c];

      // コストが低ければスキップ
      if (cost < 3000)
        continue;

      int group_i = point_to_group[pi];
      int group_j = point_to_group[pj];

      // 同じグループ内の結合なら、点を別グループとスワップすることを試みる
      if (group_i == group_j) {
        // pi または pj を他のグループの点とスワップ
        for (int target_point : {pi, pj}) {
          // スワップ候補をスコアでソート（target_pointとの近さで）
          vector<pair<double, pair<int, int>>>
              candidates; // (score, (group, point))

          for (int other_group = 0; other_group < M; ++other_group) {
            if (other_group == group_i)
              continue;

            for (int swap_point : best_groups[other_group]) {
              // target_point が other_group に行ったときの距離
              double dist_target_to_other = 0;
              for (int pid : best_groups[other_group]) {
                if (pid != swap_point) {
                  dist_target_to_other +=
                      torus_dist(points[target_point], points[pid]);
                }
              }

              // swap_point が group_i に行ったときの距離
              double dist_swap_to_orig = 0;
              for (int pid : best_groups[group_i]) {
                if (pid != target_point) {
                  dist_swap_to_orig +=
                      torus_dist(points[swap_point], points[pid]);
                }
              }

              double score = dist_target_to_other + dist_swap_to_orig;
              candidates.push_back({score, {other_group, swap_point}});
            }
          }

          // スコアが小さい順にソート
          sort(candidates.begin(), candidates.end());

          // 上位の候補だけ試す
          int max_try = min(10, (int)candidates.size());
          for (int i = 0; i < max_try && !improved; ++i) {
            // 時間チェック
            if (get_elapsed() > TIME_LIMIT)
              break;

            auto [score, gp] = candidates[i];
            int other_group = gp.first;
            int swap_point = gp.second;

            // target_point と swap_point をスワップ
            vector<vector<int>> new_groups = best_groups;

            // target_point を group_i から削除し other_group に追加
            auto &gi = new_groups[group_i];
            gi.erase(remove(gi.begin(), gi.end(), target_point), gi.end());
            new_groups[other_group].push_back(target_point);

            // swap_point を other_group から削除し group_i に追加
            auto &go = new_groups[other_group];
            go.erase(remove(go.begin(), go.end(), swap_point), go.end());
            new_groups[group_i].push_back(swap_point);

            // 新しい解を評価
            auto new_ops = make_ops_greedy(new_groups, points, N - M, T);
            long long new_cost = calc_ops_cost(new_ops, points, N, T, L);

            if (new_cost < best_total_cost) {
              best_total_cost = new_cost;
              best_ops = new_ops;
              best_groups = new_groups;
              improved = true;
            }
          }
          if (improved)
            break;
        }
      }
    }

    if (!improved)
      break;
  }

  auto &ops = best_ops;

  for (const auto &[t, i, j] : ops) {
    cout << t << ' ' << i << ' ' << j << '\n';
  }

  return 0;
}

Submission Info

Compile Error

./Main.cpp: In function 'std::vector<std::tuple<int, int, int> > make_ops_greedy(const std::vector<std::vector<int> >&, const std::vector<Point>&, int, int)':
./Main.cpp:170:50: warning: unused parameter 'limit' [-Wunused-parameter]
  170 |                                              int limit, int T) {
      |                                              ~~~~^~~~~

Judge Result