結果
問題 | No.5007 Steiner Space Travel |
ユーザー |
![]() |
提出日時 | 2022-07-30 14:39:46 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 984 ms / 1,000 ms |
コード長 | 3,432 bytes |
コンパイル時間 | 776 ms |
実行使用メモリ | 5,164 KB |
スコア | 6,594,836 |
最終ジャッジ日時 | 2022-07-30 14:40:19 |
合計ジャッジ時間 | 32,442 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge10 |
純コード判定しない問題か言語 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 30 |
ソースコード
#include <cmath>#include <ctime>#include <vector>#include <iostream>#include <algorithm>using namespace std;namespace myrandom {uint64_t seed = 123456789ULL;uint64_t xorshift64() {seed ^= seed << 13;seed ^= seed >> 7;seed ^= seed << 17;return seed;}int next_int(int l, int r) {return l + int(xorshift64() % (r - l));}double next_double(double l, double r) {return l + double(xorshift64()) / double(uint64_t(-1)) * (r - l);}}class point2d {public:int x, y;point2d() : x(0), y(0) {};point2d(int x_, int y_) : x(x_), y(y_) {};point2d& operator+=(const point2d& p) {x += p.x;y += p.y;return (*this);}point2d& operator-=(const point2d& p) {x -= p.x;y -= p.y;return (*this);}point2d operator+(const point2d& p) const {return point2d(*this) += p;}point2d operator-(const point2d& p) const {return point2d(*this) -= p;}int norm() const {return x * x + y * y;}};class answer_container {public:vector<point2d> stations;vector<pair<int, int> > path;answer_container() : stations(vector<point2d>()), path(vector<pair<int, int> >()) {};answer_container(const std::vector<point2d>& stations_, const std::vector<pair<int, int> >& path_) : stations(stations_), path(path_) {};};answer_container solve(int N, int M, const std::vector<point2d>& P) {const int INF = 1012345678;const double TLE = 0.95;int initial_t = clock();vector<int> best_perm;int best_cost = INF;int loops = 0;while (double(clock() - initial_t) / CLOCKS_PER_SEC < TLE) {vector<int> perm(N + 1);for (int i = 0; i <= N; i++) {perm[i] = i % N;}for (int i = 1; i <= N - 1; i++) {swap(perm[i], perm[myrandom::next_int(1, i + 1)]);}int cost = 0;for (int i = 0; i < N; i++) {cost += (P[perm[i]] - P[perm[i + 1]]).norm();}int cont = 0;while (cont < 2 * N * N) {cont += 1;int vl, vr;do {vl = myrandom::next_int(1, N + 1);vr = myrandom::next_int(1, N + 1);if (vl > vr) {swap(vl, vr);}} while (vr - vl <= 1);int next_cost = cost;next_cost -= (P[perm[vl - 1]] - P[perm[vl]]).norm();next_cost -= (P[perm[vr - 1]] - P[perm[vr]]).norm();next_cost += (P[perm[vl - 1]] - P[perm[vr - 1]]).norm();next_cost += (P[perm[vl]] - P[perm[vr]]).norm();if (cost >= next_cost) {if (cost > next_cost) {cont = 0;}cost = next_cost;reverse(perm.begin() + vl, perm.begin() + vr);}}if (best_cost > cost) {best_cost = cost;best_perm = perm;cerr << "Loop #" << loops << ": Cost = " << cost << endl;}loops += 1;}cerr << "Total Loops = " << loops << endl;cerr << "Final Cost = " << best_cost * 25 << endl;cerr << "Final Score = " << fixed << 1.0e+9 / (1.0e+3 + sqrt(best_cost * 25)) << endl;vector<pair<int, int> > path;for (int i = 0; i <= N; i++) {path.push_back(make_pair(1, best_perm[i]));}return answer_container(vector<point2d>(M, point2d()), path);}int main() {int N, M;cin >> N >> M;vector<point2d> P(N);for (int i = 0; i < N; i++) {cin >> P[i].x >> P[i].y;}answer_container answer = solve(N, M, P);for (int i = 0; i < M; i++) {cout << answer.stations[i].x << ' ' << answer.stations[i].y << endl;}cout << answer.path.size() << endl;for (int i = 0; i < int(answer.path.size()); i++) {cout << answer.path[i].first << ' ' << answer.path[i].second + 1 << endl;}return 0;}