結果

問題 No.5007 Steiner Space Travel
コンテスト
ユーザー olphe
提出日時 2022-07-30 15:37:53
言語 C++17(gcc12)
(gcc 12.3.0 + boost 1.87.0)
結果
AC  
実行時間 26 ms / 1,000 ms
コード長 2,806 bytes
コンパイル時間 1,456 ms
実行使用メモリ 6,952 KB
スコア 7,121,713
最終ジャッジ日時 2022-07-30 15:37:59
合計ジャッジ時間 3,936 ms
ジャッジサーバーID
（参考情報） 		judge10 / judge14
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include "iostream"
#include "climits"
#include "list"
#include "queue"
#include "stack"
#include "set"
#include "functional"
#include "algorithm"
#include "string"
#include "map"
#include "unordered_map"
#include "unordered_set"
#include "iomanip"
#include "cmath"
#include "random"
#include "bitset"
#include "cstdio"
#include "numeric"
#include "cassert"
#include "ctime"

using namespace std;

constexpr int by = 5;

int N, M;
vector<int>x;
vector<int>y;
vector<int>ans;

class XorShift {
	unsigned int x, y, z, w, t;
public:
	XorShift() {
		x = 133553533;
		y = 314867339;
		z = 664298413;
		w = 999999937;
		t = 0;
	}
	unsigned int rand() {
		t = x ^ (x << 11);
		x = y;
		y = z;
		z = w;
		w = (w ^ (w >> 19)) ^ (t ^ (t >> 8));
		return w & 0x7fffffff;
	}
};

XorShift xs;

void Initialize() {
	cin >> N >> M;
	x.resize(N);
	y.resize(N);
	for (int i = 0; i < N; i++) {
		cin >> x[i] >> y[i];
	}

}

void Station() {
	for (int i = 0; i < M; i++) {
		x.push_back(xs.rand() % 1000);
		y.push_back(xs.rand() % 1000);
	}
}

void TSP() {
	vector<vector<double>>dis(N, vector<double>(N));
	vector<vector<vector<int>>>use(N, vector<vector<int>>(N));
	for (int i = 0; i < N; i++) {
		for (int j = i + 1; j < N; j++) {
			dis[j][i] = dis[i][j] = hypot(x[i] - x[j], y[i] - y[j]) * by * by;
			for (int k = 0; k < M; k++) {
				for (int l = 0; l < M; l++) {
					double c = hypot(x[i] - x[N + k], y[i] - y[N + k]) * by + hypot(x[N + k] - x[N + l], y[N + k] - y[N + l]) + hypot(x[N + l] - x[j], y[N + l] - y[j]) * by;
					if (c < dis[i][j]) {
						dis[i][j] = c;
						use[i][j] = { N+k,N+l };
						use[j][i] = { N+l,N+k };
						dis[j][i] = c;
					}
				}
			}
		}
	}
	vector<int>route(N + 1);
	for (int i = 0; i < N + 1; i++) {
		route[i] = i % N;
	}
	for (int loop = 0; loop < 100000; loop++) {
		int a = xs.rand() % (N - 1);
		int b = xs.rand() % (N - 2) + a + 1; 
		b %= N - 1;
		if (a > b)swap(a, b);
		a++;
		b += 2;
		double bef = dis[route[a - 1]][route[a]] + dis[route[b - 1]][route[b]];
		double aft = dis[route[a - 1]][route[b - 1]] + dis[route[a]][route[b]];
		if (bef > aft) {
			reverse(route.begin() + a, route.begin() + b);
		}
		else {

		}
	}
	ans.push_back(route[0]);
	cerr << "----------------" << endl;
	for (int i = 0; i < N; i++) {
		if (use[route[i]][route[i + 1]].size()) {
			ans.push_back(use[route[i]][route[i + 1]][0]);
			ans.push_back(use[route[i]][route[i + 1]][1]);
		}
		ans.push_back(route[i+1]);
	}
}

void Output() {
	for (int i = N; i < x.size(); i++) {
		cout << x[i] << " " << y[i] << endl;
	}
	cout << ans.size() << endl;
	for (auto i : ans) {
		if (i < N) {
			cout << 1 << " " << i + 1 << endl;
		}
		else {
			cout << 2 << " " << i - N + 1 << endl;
		}
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);

	Initialize();
	Station();
	TSP();
	Output();
}
0