結果

問題 No.5007 Steiner Space Travel
ユーザー olpheolphe
提出日時 2022-07-30 17:14:33
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
TLE  
実行時間 -
コード長 4,131 bytes
コンパイル時間 1,579 ms
実行使用メモリ 6,952 KB
スコア 0
最終ジャッジ日時 2022-07-30 17:16:19
合計ジャッジ時間 49,491 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 TLE -
testcase_01 TLE -
testcase_02 TLE -
testcase_03 TLE -
testcase_04 TLE -
testcase_05 TLE -
testcase_06 TLE -
testcase_07 TLE -
testcase_08 TLE -
testcase_09 TLE -
testcase_10 TLE -
testcase_11 TLE -
testcase_12 TLE -
testcase_13 TLE -
testcase_14 TLE -
testcase_15 TLE -
testcase_16 TLE -
testcase_17 TLE -
testcase_18 TLE -
testcase_19 TLE -
testcase_20 TLE -
testcase_21 TLE -
testcase_22 TLE -
testcase_23 TLE -
testcase_24 TLE -
testcase_25 TLE -
testcase_26 TLE -
testcase_27 TLE -
testcase_28 TLE -
testcase_29 TLE -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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];
	}

}


int Score(vector<vector<int>>dis, vector<int>route) {
	int sum = 0;
	for (int i = 1; i < route.size(); i++) {
		sum += dis[route[i - 1]][route[i]];
	}
	return round(1e9 / (1000 + sqrt(sum)));
}

int Dist(int x1, int x2, int y1, int y2) {
	return (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2);
}

void Station() {
	vector<int>cl(N);
	for (int i = 0; i < N; i++) {
		cl[i] = xs.rand() % M;
	}
	vector<double>cx(M);
	vector<double>cy(M);
	for (int i = 0; i < 100; i++) {
		for (auto& i : cx)i = 0;
		for (auto& i : cy)i = 0;
		vector<int>cxnum(M);
		vector<int>cynum(M);
		for (int i = 0; i < N; i++) {
			cx[cl[i]] += x[i];
			cy[cl[i]] += y[i];
			cxnum[cl[i]]++;
			cynum[cl[i]]++;
		}
		for (int i = 0; i < M; i++) {
			if (cxnum[i]) {
				cx[i] /= cxnum[i];
				cy[i] /= cynum[i];
			}
		}
		for (int j = 0; j < N; j++) {
			for (int k = 0; k < M; k++) {
				if (Dist(x[j], cx[cl[j]], y[j], cy[cl[j]]) > Dist(x[j], cx[k], y[j], cy[k])) {
					cl[j] = k;
				}
			}
		}

	}
	for (int i = 0; i < M; i++) {
		x.push_back(round(cx[i]));
		y.push_back(round(cy[i]));
	}
}

int bestscore = 0;
vector<int>outx;
vector<int>outy;


void TSP() {

	vector<vector<int>>dis(N, vector<int>(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] = Dist(x[i], x[j], y[i], y[j]) * by * by;
			for (int k = 0; k < M; k++) {
				for (int l = 0; l < M; l++) {
					int c = Dist(x[i], x[N + k], y[i], y[N + k]) * by + Dist(x[N + k], x[N + l], y[N + k], y[N + l]) + Dist(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 < 20000; 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 {

		}
	}
	int score = Score(dis, route);
	cerr << score << endl;
	if (bestscore < score) {
		bestscore = score;
		ans.clear();
		outx.clear();
		outy.clear();
		for (int i = N; i < x.size(); i++) {
			outx.push_back(x[i]);
			outy.push_back(y[i]);
		}
		ans.push_back(route[0]);
		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() {
	cerr << "----------------" << endl;
	for (int i = 0; i < outx.size(); i++) {
		cout << outx[i] << " " << outy[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();
	for (int i = 0; i < 500; i++) {
		Station();
		TSP();
		x.resize(N);
		y.resize(N);
	}
	Output();
}
0