結果
問題 | No.5007 Steiner Space Travel |
ユーザー |
![]() |
提出日時 | 2022-07-30 15:52:10 |
言語 | C++17(clang) (17.0.6 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 902 ms / 1,000 ms |
コード長 | 7,682 bytes |
コンパイル時間 | 30,181 ms |
実行使用メモリ | 4,188 KB |
スコア | 7,458,054 |
最終ジャッジ日時 | 2022-07-31 03:13:10 |
合計ジャッジ時間 | 31,562 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge11 |
純コード判定しない問題か言語 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 30 |
コンパイルメッセージ
main.cpp:130:26: warning: variable 'k' is uninitialized when used within its own initialization [-Wuninitialized] for (int k = k+1; k < m; k++) { ~ ^ 1 warning generated.
ソースコード
#include <algorithm>#include <iostream>#include <cstdio>#include <map>#include <numeric>#include <cmath>#include <set>#include <sstream>#include <string>#include <vector>#include <queue>#include <stack>#include <complex>#include <string.h>#include <unordered_set>#include <unordered_map>#include <bitset>#include <iomanip>#include <sys/time.h>#include <tuple>#include <random>using namespace std;#define endl '\n'#define ALL(v) (v).begin(), (v).end()#define RALL(v) (v).rbegin(), (v).rend()#define UNIQ(v) (v).erase(unique((v).begin(), (v).end()), (v).end())typedef long long ll;typedef long double ld;typedef pair<int, int> P;typedef complex<double> comp;typedef vector< vector<ld> > matrix;struct pairhash {public:template<typename T, typename U>size_t operator()(const pair<T, U> &x) const {size_t seed = hash<T>()(x.first);return hash<U>()(x.second) + 0x9e3779b9 + (seed<<6) + (seed>>2);}};const int INF = 1e9 + 9;//const ll INF = 1e18 + 9;const ll MOD = 1e9 + 7;//const ll MOD = 998244353;const double EPS = 1e-8;const double PI = acos(-1);int n, m;int a[110], b[110];int dist[110][110];const int alpha = 5;const int alpha2 = 25;double get_elapsed_time(struct timeval *begin, struct timeval *end) {return (end->tv_sec - begin->tv_sec) * 1000+ (end->tv_usec - begin->tv_usec) / 1000.0;}unsigned long xor128(void) {static unsigned long x=123456789,y=362436069,z=521288629,w=88675123;unsigned long t;t=(x^(x<<11));x=y;y=z;z=w; return( w=(w^(w>>19))^(t^(t>>8)) );}// [0, k)int rand(int k) {return xor128() % k;}// [a, b)int rand(int a, int b) {return a + xor128() % (b - a);}// [0, 1)double rand_double() {return (double)rand(INF) / INF;}int calc_dist(const int i, const int j) {return (a[i] - a[j]) * (a[i] - a[j]) + (b[i] - b[j]) * (b[i] - b[j]);}int calc_dist(const int i, const pair<int, int>& p) {return (a[i] - p.first) * (a[i] - p.first) + (b[i] - p.second) * (b[i] - p.second);}int calc_dist(const pair<int, int>& p0, const pair<int, int>& p1) {return (p0.first - p1.first) * (p0.first - p1.first) + (p0.second - p1.second) * (p0.second - p1.second);}int calc_diff(const int i, const int j, const vector<int>& order) {const int i0 = order[i], i1 = order[i-1];const int j0 = order[j], j1 = order[j+1];const int d_cur = dist[i1][i0] + dist[j0][j1];const int d_next = dist[i1][j0] + dist[i0][j1];return d_cur - d_next;}int calc_diff_s(const int i, const int j, const vector<int>& order, const vector<int>& order_rev, const vector<int>& exist) {const int order_i = order_rev[i], order_j = order_rev[j];const int i_prev = order[max(0, order_i-1)];const int i_next = order[order_i+1];const int j_prev = order[max(0, order_j-1)];const int j_next = order[order_j+1];int d_cur = 0;d_cur += (exist[i_prev] >= 0 ? dist[i_prev][i] : alpha * dist[i_prev][i]);d_cur += (exist[i_next] >= 0 ? dist[i][i_next] : alpha * dist[i][i_next]);d_cur += (exist[j_prev] >= 0 ? alpha * dist[j_prev][j] : alpha2 * dist[j_prev][j]);d_cur += (exist[j_next] >= 0 ? alpha * dist[j][j_next] : alpha2 * dist[j][j_next]);int d_next = 0;d_next += (exist[i_prev] >= 0 ? alpha * dist[i_prev][i] : alpha2 * dist[i_prev][i]);d_next += (exist[i_next] >= 0 ? alpha * dist[i][i_next] : alpha2 * dist[i][i_next]);d_next += (exist[j_prev] >= 0 ? dist[j_prev][j] : alpha * dist[j_prev][j]);d_next += (exist[j_next] >= 0 ? dist[j][j_next] : alpha * dist[j][j_next]);return d_cur - d_next;}int calc_tour_dist(const vector<int>& order, const vector<pair<int, int>>& stations) {int d = 0;for (int i = 0; i < n; i++) {int d0 = alpha2 * dist[order[i]][order[i+1]];for (const auto& p : stations) {d0 = min(d0, alpha * (calc_dist(order[i], p) + calc_dist(order[i+1], p)));}for (int j = 0; j < m; j++) {for (int k = k+1; k < m; k++) {d0 = min(d0, alpha * calc_dist(order[i], stations[j]) + calc_dist(stations[j], stations[k]) + alpha * calc_dist(order[i+1],stations[k]));}}d += d0;}return d;}void init() {for (int i = 0; i < n; i++)for (int j = 0; j < n; j++)dist[i][j] = calc_dist(i, j);}pair<vector<pair<int, int>>, vector<pair<int, int>>> solve() {init();vector<int> order;for (int i = 0; i < n; i++) order.push_back(i);order.push_back(0);struct timeval t1, t2;gettimeofday(&t1, NULL);int iter;double T_init = 10;double T_end = 0.01;double T = T_init;double TIME_LIMIT = 100;int move = 0;for (iter = 1; ; iter++) {int i, j;i = rand(1, n);while (i == (j = rand(1, n)));if (i > j) swap(i, j);const int diff = calc_diff(i, j, order);if (diff > 0 || exp(diff/T) > rand_double()) {reverse(order.begin()+i, order.begin()+j+1);}if (iter % 100 == 0) {gettimeofday(&t2, NULL);const double et = get_elapsed_time(&t1, &t2);if (et > TIME_LIMIT) break;T = (T_end - T_init) / TIME_LIMIT * et + T_init;}}vector<int> order_rev(n);for (int i = 0; i < n; i++) {order_rev[order[i]] = i;}int p[n];for (int i = 0; i < n; i++) p[i] = i;vector<int> s_pos;vector<int> exist(n, -1);for (int i = 0; i < m; i++) {const int j = rand(n-i);s_pos.push_back(p[j]);exist[p[j]] = i;swap(p[j], p[n-i-1]);}gettimeofday(&t1, NULL);T_init = 200000;T_end = 0.01;T = T_init;TIME_LIMIT = 800;move = 0;for (iter = 1; ; iter++) {const int s_idx = rand(m);const int i = s_pos[s_idx];int j;while (true) {j = rand(n);if (exist[j] < 0) break;}const int diff = calc_diff_s(i, j, order, order_rev, exist);if (diff > 0 || exp(diff/T) > rand_double()) {s_pos[s_idx] = j;exist[i] = -1;exist[j] = s_idx;move++;}if (iter % 100 == 0) {gettimeofday(&t2, NULL);const double et = get_elapsed_time(&t1, &t2);if (et > TIME_LIMIT) break;T = (T_end - T_init) / TIME_LIMIT * et + T_init;}}cerr << "iter: " << iter << endl;cerr << "move: " << move << endl;vector<pair<int, int>> stations;for (int i = 0; i < m; i++) {const int idx = s_pos[i];stations.push_back(make_pair(a[idx], b[idx]));}vector<pair<int, int>> res;for (int i = 0; i <= n; i++) {const int v = order[i];const int s_idx = exist[v];if (i > 0 && s_idx >= 0) res.push_back(make_pair(2, s_idx+1));res.push_back(make_pair(1, v+1));if (i < n && s_idx >= 0) res.push_back(make_pair(2, s_idx+1));}return make_pair(stations, res);}void input() {cin >> n >> m;for (int i = 0; i < n; i++) cin >> a[i] >> b[i];}void output(const pair<vector<pair<int, int>>, vector<pair<int, int>>>& res) {for (const auto& s : res.first) {cout << s.first << " " << s.second << endl;}cout << (int)res.second.size() << endl;for (const auto& s : res.second) {cout << s.first << " " << s.second << endl;}}int main() {ios::sync_with_stdio(false);cin.tie(0);cout << fixed << setprecision(15);input();const auto& res = solve();output(res);}