結果
問題 | No.5007 Steiner Space Travel |
ユーザー |
![]() |
提出日時 | 2022-07-30 15:02:49 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 503 ms / 1,000 ms |
コード長 | 10,227 bytes |
コンパイル時間 | 2,864 ms |
実行使用メモリ | 3,848 KB |
スコア | 4,769,099 |
最終ジャッジ日時 | 2022-07-30 15:03:10 |
合計ジャッジ時間 | 20,205 ms |
ジャッジサーバーID (参考情報) |
judge10 / judge15 |
純コード判定しない問題か言語 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 30 |
ソースコード
#include <bits/stdc++.h>using namespace std;u_int64_t seed = 91;u_int64_t xor_shift(){seed ^= seed << 1;seed ^= seed >> 3;seed ^= seed << 10;return seed;}class Time{public:chrono::system_clock::time_point start_time;Time(){start_time = now();}chrono::system_clock::time_point now(){return chrono::system_clock::now();}int elapsed(){auto cur = chrono::system_clock::now();return chrono::duration_cast<chrono::milliseconds>(cur - start_time).count();}};template <class T>class TSP{vector<vector<T>> D;vector<int> ans, A, v_to_cycle;vector<vector<int>> nearest;int n;T INF;public:TSP (vector<vector<T>> D, T INF): D(D), n(D.size()), INF(INF){ans.resize(n);iota(ans.begin(), ans.end(), 0);v_to_cycle.resize(n);iota(v_to_cycle.begin(), v_to_cycle.end(), 0);A.resize(n);iota(A.begin(), A.end(), 0);nearest.assign(n, vector<int>(n));for (int i = 0; i < n; i++){vector<pair<T, int>> B(n);for (int j = 0; j < n; j++)B[j] = {D[i][j], j};sort(B.begin(), B.end());for (int j = 0; j < n; j++)nearest[i][j] = B[j].second;}};vector<int> solve_perm(){vector<int> P(n);iota(P.begin(), P.end(), 0);T best_score = INF;vector<int> best = P;do {T s = calc_score(P);if (s < best_score){best = P;best_score = s;}} while (next_permutation(P.begin(), P.end()));return best;}vector<int> solve(int time_limit){if (n < 10)return solve_perm();Time time;// // initial 2-opt// while (true){// bool updated = false;// for (int t1 = 0; t1 < n; t1++){// int t2 = (t1 + 1) % n;// for (const auto &v: nearest[ans[t2]]){// int t3 = v_to_cycle[v];// if (dist(t1, t2) <= dist(t2, t3))// break;// int t4 = (t3 - 1 + n) % n;// int i, j;// if (t2 <= t4)// tie(i, j) = {t2, t4};// else// tie(i, j) = {t3, t1};// const auto d = calc_two_opt_score(i, j);// if (d < 0){// two_opt_swap(i, j);// updated = true;// }// }// }// if (!updated)// break;// }// kick (double bridge + 2-opt)auto best = ans;auto best_v_to_cycle = v_to_cycle;T score = calc_score(ans);int loop = 0;while (time.elapsed() < time_limit){loop++;ans = best;v_to_cycle = best_v_to_cycle;// kickT diff = 0;{auto chosen = choose_k(4);sort(chosen.begin(), chosen.end());diff = calc_double_bridge(chosen[0], chosen[1], chosen[2], chosen[3]);double_birdge(chosen[0], chosen[1], chosen[2], chosen[3]);}// // random 2-opt// for (int i = 0; i < 6; i++){// const int a = xor_shift() % n;// const int b = xor_shift() % n;// diff += calc_two_opt_score(a, b);// two_opt_swap(a, b);// }vector<int> Q(n);iota(Q.begin(), Q.end(), 0);// local optimizationwhile (true){bool updated = false;vector<int> NQ;for (auto u: Q){int t1 = v_to_cycle[u];int t2 = (t1 + 1) % n;for (const auto &v: nearest[ans[t2]]){int t3 = v_to_cycle[v];if (dist(t1, t2) <= dist(t2, t3))break;int t4 = (t3 - 1 + n) % n;int i, j;if (t2 <= t4)tie(i, j) = {t2, t4};elsetie(i, j) = {t3, t1};const auto d = calc_two_opt_score(i, j);if (d < 0){NQ.push_back(ans[(t1 - 1 + n) % n]);NQ.push_back(ans[t1]);NQ.push_back(ans[t2]);NQ.push_back(ans[(t2 + 1) % n]);NQ.push_back(ans[(t4 - 1 + n) % n]);NQ.push_back(ans[t3]);NQ.push_back(ans[t4]);NQ.push_back(ans[(t3 + 1) % n]);two_opt_swap(i, j);diff += d;updated = true;break;}}}if (!updated)break;Q = NQ;sort(Q.begin(), Q.end());Q.erase(unique(Q.begin(), Q.end()), Q.end());}if (diff < 0){best = ans;best_v_to_cycle = v_to_cycle;score += diff;cerr << score << endl;}}cerr << "loop: " << loop << endl;// cerr << score << endl;return best;}T dist(int i, int j){// こっちに%n押し付けたいだろif (i < 0)i += n;if (i >= n)i -= n;if (j < 0)j += n;if (j >= n)j -= n;return D[ans[i]][ans[j]];}T dist(int i, int j, const vector<int> &ans){return D[ans[i]][ans[j]];}T calc_score(const vector<int> &ans){T res = 0;assert(ans.size() > 0);for (int i = 0; i < ans.size() - 1; i++)res += dist(i, i + 1, ans);res += dist(ans.size() - 1, 0, ans);return res;}T calc_two_opt_score(int i, int j){T res = 0;if (i > j)swap(i, j);if (i == 0 and j == n - 1)return 0;res += dist((i - 1 + n) % n, j) - dist((i - 1 + n) % n, i);res += dist(i, (j + 1) % n) - dist(j, (j + 1) % n);return res;}void two_opt_swap(int i, int j){if (i > j)swap(i, j);reverse(ans.begin() + i, ans.begin() + j + 1);for (int a = i; a <= j; a++)v_to_cycle[ans[a]] = a;}T three_opt_swap(int i, int j, int k){assert(i < j and j < k);array<T, 5> d;i--; j--; k--; // バカd[0] = dist(i, i + 1) + dist(j, j + 1) + dist(k, k + 1);d[1] = dist(i, j) + dist(i + 1, j + 1) + dist(k, k + 1);d[2] = dist(i, i + 1) + dist(j, k) + dist(j + 1, k + 1);d[3] = dist(i, j + 1) + dist(k, i + 1) + dist(j, k + 1);d[4] = dist(k + 1, i + 1) + dist(j, j + 1) + dist(k, i);i++; j++; k++;if (d[0] > d[1]){reverse(ans.begin() + i, ans.begin() + j);return -d[0] + d[1];} else if (d[0] > d[2]){reverse(ans.begin() + j, ans.begin() + k);return -d[0] + d[2];} else if (d[0] > d[4]){reverse(ans.begin() + i, ans.begin() + k);return -d[0] + d[4];} else if (d[0] > d[3]){vector<int> tmp(k - i);copy(ans.begin() + j, ans.begin() + k, tmp.begin());copy(ans.begin() + i, ans.begin() + j, tmp.begin() + k - j);copy(tmp.begin(), tmp.end(), ans.begin() + i);return -d[0] + d[3];}return 0;}T calc_double_bridge(int i, int j, int k, int l){assert(i < j and j < k and k < l);T res = 0;res -= dist(i, i + 1) + dist(j, j + 1) + dist(k, k + 1) + dist(l, (l + 1) % n);res += dist(i, k + 1) + dist(j, (l + 1) % n) + dist(k, i + 1) + dist(l, j + 1);return res;}void double_birdge(int i, int j, int k, int l){assert(i < j and j < k and k < l);assert(l < n);vector<int> res(n);copy(ans.begin(), ans.begin() + i + 1, res.begin());copy(ans.begin() + k + 1, ans.begin() + l + 1, res.begin() + i + 1);copy(ans.begin() + j + 1, ans.begin() + k + 1, res.begin() + i + l - k + 1);copy(ans.begin() + i + 1, ans.begin() + j + 1, res.begin() + i + l - j + 1);copy(ans.begin() + l + 1, ans.end(), res.begin() + l + 1);ans = res;for (int a = 0; a < n; a++)v_to_cycle[ans[a]] = a;}vector<int> choose_k(int k){const int m = A.size();assert(k <= m);vector<int> res(k);for (int i = 0; i < k; i++){int r = i + xor_shift() % (m - i);swap(A[i], A[r]);res[i] = A[i];}return res;}};int main(){int n, m;cin >> n >> m;vector<int> A(n), B(n);for (int i = 0; i < n; i++)cin >> A[i] >> B[i];constexpr int alpha = 5;vector<vector<int64_t>> D(n, vector<int64_t>(n));for (int i = 0; i < n; i++){for (int j = 0; j < n; j++){D[i][j] = (A[i] - A[j]) * (A[i] - A[j]) + (B[i] - B[j]) * (B[i] - B[j]) * alpha * alpha;}}TSP tsp(D, int64_t(1e15));auto ans = tsp.solve(500);cerr << tsp.calc_score(ans) << endl;for (int i = 0; i < m; i++)cout << "0 0" << endl;for (int i = 0; i < n; i++){if (ans[i] == 0)rotate(ans.begin(), ans.begin() + i, ans.end());}assert(ans[0] == 0);cout << n + 1 << endl;for (const auto &a: ans)cout << "1 " << a + 1 << endl;cout << "1 1" << endl;}