結果

問題 No.5007 Steiner Space Travel
ユーザー square1001
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0