結果
問題 | No.5007 Steiner Space Travel |
ユーザー |
![]() |
提出日時 | 2022-07-30 14:08:49 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 222 ms / 1,000 ms |
コード長 | 6,255 bytes |
コンパイル時間 | 3,194 ms |
実行使用メモリ | 3,900 KB |
スコア | 4,772,571 |
最終ジャッジ日時 | 2022-07-30 14:09:00 |
合計ジャッジ時間 | 10,039 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge12 |
純コード判定しない問題か言語 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 30 |
ソースコード
#include <bits/stdc++.h>// #include "atcoder/all"using namespace std;using i64 = long long;const i64 MOD = 1e9 + 7;const i64 INF = i64(1e18);template <typename T>bool chmin(T& x, T y){if(x > y){x = y;return true;}return false;}template <typename T>bool chmax(T& x, T y){if(x < y){x = y;return true;}return false;}uint32_t rnd(){static uint32_t x = 123456789, y = 362436069, z = 521288629, w = 0;uint32_t t = x ^ (x << 11);x = y;y = z;z = w;w = (w ^ (w >> 19)) ^ (t ^ (t >> 8));return w;}double rnd_double(){return 1.0 * rnd() / numeric_limits<uint32_t>::max();}// #define OPTIMIZEnamespace params{void load_params(){ifstream ifs("../params.txt");assert(ifs.is_open());}}// doc: https://shibh308.github.io/library/library/lib/functions/tsp.cpp.htmltemplate<typename T>vector<int> tsp(int n, vector<vector<T>> dist){// 始点=終点のTSP n <= 2 とかでバグりそうなので注意vector<int> v(n);vector<int> inv(n);// 適当に初期解を生成iota(v.begin(), v.end(), 0);T now_dist = 0;for(int i = 0; i < n; ++i){inv[v[i]] = i;now_dist += dist[v[i]][v[(i + 1) % n]];}// 前計算vector<vector<pair<T,int>>> near_vertexes(n);for(int i = 0; i < n; ++i){for(int j = 0; j < n; ++j){near_vertexes[i].emplace_back(dist[i][j], j);}sort(near_vertexes[i].begin(), near_vertexes[i].end());}auto dist_check = [&](){auto di = dist[0][0];for(int i = 0; i < n; ++i){di += dist[v[i]][v[(i + 1) % n]];}assert(abs(now_dist - di) <= 1e-6);};auto update = [&](int i1, int i3){int i2 = (i1 + 1) % n;int i4 = (i3 + 1) % n;if(i1 == i3 || i2 == i3 || i1 == i4 || i2 == i4)return false;if(dist[v[i1]][v[i2]] + dist[v[i3]][v[i4]] <= dist[v[i1]][v[i3]] + dist[v[i2]][v[i4]])return false;auto improve = (dist[v[i1]][v[i2]] + dist[v[i3]][v[i4]]) - (dist[v[i1]][v[i3]] + dist[v[i2]][v[i4]]);now_dist -= improve;int d1 = (i2 < i3 ? i3 - i2 : i3 + n - i2);int d2 = (i4 < i1 ? i1 - i4 : i1 + n - i4);if(d1 >= d2){swap(i1, i3);swap(i2, i4);}int st = i2;int en = i2 < i3 ? i3 : i3 + n;while(st < en){inv[v[en % n]] = st % n;inv[v[st % n]] = en % n;swap(v[st % n], v[en % n]);++st, --en;}// バグが怖い時用// dist_check();return true;};auto neighbors_search = [&](){for(int i = 0; i < n; ++i){int idx1 = i;int idx2 = (i + 1) % n;int v1 = v[idx1];int v2 = v[idx2];for(auto [d, v3] : near_vertexes[v1]){if(v3 == v2)break;int idx3 = inv[v3];if(update(idx1, idx3)){return true;}}for(auto [d, v4] : near_vertexes[v2]){if(v4 == v1)break;int idx3 = (inv[v4] + n - 1) % n;if(update(idx1, idx3)){return true;}}}return false;};auto double_bridge = [&](){vector<uint32_t> r{rnd() % n, rnd() % n, rnd() % n, rnd() % n};sort(r.begin(), r.end());if(r[0] == r[1] || r[1] == r[2] || r[2] == r[3]){return true;}// (r[3] + 1, r[0]) => (r[2] + 1, r[3]) => (r[1] + 1, r[2]) => (r[0] + 1, r[1])auto diff = dist[0][0];diff -= dist[v[r[0]]][v[r[0] + 1]];diff -= dist[v[r[1]]][v[r[1] + 1]];diff -= dist[v[r[2]]][v[r[2] + 1]];diff -= dist[v[r[3]]][v[(r[3] + 1) % n]];diff += dist[v[r[0]]][v[r[2] + 1]];diff += dist[v[r[3]]][v[r[1] + 1]];diff += dist[v[r[2]]][v[r[0] + 1]];diff += dist[v[r[1]]][v[(r[3] + 1) % n]];now_dist += diff;vector<int> nex;nex.reserve(n);for(int i = r[3] + 1; i < n; ++i)nex.emplace_back(v[i]);for(int i = 0; i <= r[0]; ++i)nex.emplace_back(v[i]);for(int i = r[2] + 1; i <= r[3]; ++i)nex.emplace_back(v[i]);for(int i = r[1] + 1; i <= r[2]; ++i)nex.emplace_back(v[i]);for(int i = r[0] + 1; i <= r[1]; ++i)nex.emplace_back(v[i]);v = move(nex);return false;};auto best = make_pair(now_dist, v);for(int i = 0; i < 1000; ++i){if(i){while(double_bridge());}while(neighbors_search());if(!chmin(best, make_pair(now_dist, v))){tie(now_dist, v) = best;}}for(int i = 0; i < n; ++i){if(v[i] == 0){vector<int> res;for(int j = 0; j < n; ++j){res.emplace_back(v[(i + j) % n]);}return res;}}// return now_dist;return v;}constexpr int n = 100;constexpr int m = 8;constexpr int alpha = 5;array<int, n> ax, ay;void read_file(istream& ifs){int a;ifs >> a >> a;// TODO: inputfor(int i = 0; i < n; ++i){ifs >> ax[i] >> ay[i];}}clock_t st;void solve(){vector<vector<i64>> dist(n, vector<i64>(n));for(int i = 0; i < n; ++i){for(int j = 0; j < n; ++j){dist[i][j] = (ax[i] - ax[j]) * (ax[i] - ax[j]) + (ay[i] - ay[j]) * (ay[i] - ay[j]) * 25;}}auto res = tsp(100, dist);for(int i = 0; i < m; ++i){cout << 0 << " " << 0 << endl;}cout << res.size() + 1 << endl;for(int i = 0; i < n; ++i){cout << 1 << " " << res[i] + 1 << endl;}cout << 1 << " " << 1 << endl;}signed main(){st = clock();#ifdef OPTIMIZEparams::load_params();#endif#ifndef HANDread_file(cin);#elseifstream ifs("./tools/in/0000.txt");assert(ifs.is_open());read_file(ifs);#endifsolve();}