結果

問題 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;
}
0