結果

問題 No.5007 Steiner Space Travel
コンテスト
ユーザー hotpepsi
提出日時 2023-04-29 13:40:46
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 972 ms / 1,000 ms
コード長 5,206 bytes
コンパイル時間 1,686 ms
コンパイル使用メモリ 116,980 KB
実行使用メモリ 4,376 KB
スコア 7,828,102
最終ジャッジ日時 2023-04-29 13:41:21
合計ジャッジ時間 33,870 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge14
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <iostream>
#include <sstream>
#include <cassert>
#include <cmath>
#include <cstring>
#include <chrono>
#include <algorithm>
#include <numeric>
#include <vector>
#include <queue>
#include <string>
#include <set>
#include <map>
#include <unordered_map>
#include <random>

using namespace std;

#if defined(_MSC_VER) || defined(__APPLE_CC__)
#define LOCAL
#endif

const int TIME_LIMIT = 6000 - 100;
const int INF = 1000000000;

typedef pair<int, int> II;

std::random_device seed_gen;
std::mt19937_64 engine(seed_gen());

auto start_time = chrono::high_resolution_clock::now();
inline int get_elapsed_ms() { return int(chrono::duration_cast<chrono::milliseconds>(chrono::high_resolution_clock::now() - start_time).count()); }

struct Solver {
	int N;
	int M;
	vector<int> y, x, g;

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

	void prepare() {

	}

	int64_t get_dist(int a, int b) {
		int dx = x[b] - x[a], dy = y[b] - y[a];
		int64_t dist = dx * dx + dy * dy;
		if (a < N) dist *= 5;
		if (b < N) dist *= 5;
		return dist;
	}

	void output(const vector<int>& ans) {
		for (int i = 0; i < M; ++i) {
			cout << y[i + N] << " " << x[i + N] << endl;
		}
		cout << ans.size() << endl;
		for (int x : ans) {
			if (x < N) {
				cout << "1 " << (x + 1) << endl;
			} else {
				cout << "2 " << (x - N + 1) << endl;
			}
		}
	}

	bool classify() {
		for (int i = 0; i < N; ++i) {
			g[i] = engine() % M;
		}
		bool done = false;
		while (!done) {
			done = true;
			vector<int> xx(M), yy(M), cnt(M);
			for (int i = 0; i < N; ++i) {
				xx[g[i]] += x[i];
				yy[g[i]] += y[i];
				cnt[g[i]] += 1;
			}
			for (int i = 0; i < M; ++i) {
				if (cnt[i]) {
					xx[i] /= cnt[i];
					yy[i] /= cnt[i];
					x[N + i] = xx[i];
					y[N + i] = yy[i];
				}
			}
			for (int i = 0; i < N; ++i) {
				int md = INF, next_g = -1;
				for (int j = 0; j < M; ++j) {
					int dx = x[i] - xx[j], dy = y[i] - yy[j], d = dx * dx + dy * dy;
					if (d < md) {
						md = d;
						next_g = j;
					}
				}
				if (g[i] != next_g) {
					done = false;
					g[i] = next_g;
				}
			}
		}
		vector<int> cnt(M);
		for (int i = 0; i < N; ++i) {
			cnt[g[i]] += 1;
		}
		for (int i = 0; i < M; ++i) {
			if (cnt[i] == 0) {
				return false;
			}
		}
		return true;
	}

	vector<int> gen(int prev_point, int group, const vector<int>& points) {
		vector<int> r;
		if (points.size() > 60) {
			return r;
		}
		vector<int> closest_points(points.size());
		for (int i = 0; i < points.size(); ++i) {
			int64_t min_dist = 1LL << 60;
			int& closest = closest_points[i];
			for (int j = 0; j < points.size(); ++j) {
				if (i == j) continue;
				int64_t dist = get_dist(points[i], points[j]);
				if (dist < min_dist) {
					min_dist = dist;
					closest = j;
				}
			}
		}

		int64_t min_cost = 1LL << 60;
		for (int i = 0; i < 15; ++i) {
			int64_t cost = 0, vis = 0, all = (1LL << points.size()) - 1;
			vector<int> path;
			int p = prev_point, pi = -1;
			if (!points.empty() && points.front() == prev_point) {
				pi = 0;
				vis |= 1;
			}
			while (vis != all) {
				int next_index = -1, next = N + group;
				if (engine() % 2) {
					if (pi >= 0) {
						int next_candidate = closest_points[pi];
						if ((vis & (1LL << next_candidate)) == 0) {
							next_index = next_candidate;
							next = points[next_index];
						}
					}
				}
				while (p == next) {
					int next_candidate = engine() % points.size();
					if ((vis & (1LL << next_candidate)) == 0) {
						next_index = next_candidate;
						next = points[next_index];
					}
				}
				cost += get_dist(p, next);
				path.emplace_back(next);
				if (next_index >= 0) {
					vis |= (1LL << next_index);
				}
				pi = next_index;
				p = next;
			}
			cost += get_dist(path.empty() ? prev_point : path.back(), N + group);
			path.emplace_back(N + group);
			if (cost < min_cost) {
				min_cost = cost;
				r = path;
			}
		}
		return r;
	}

	vector<int> gen(const vector<int> &seq) {
		vector<int> r;
		r.emplace_back(0);
		for (int gg = 0; gg < M; ++gg) {
			vector<int> points;
			int target_group = seq[gg];
			for (int i = 0; i < N; ++i) {
				if (g[i] == target_group) {
					points.emplace_back(i);
				}
			}
			for (auto x : gen(r.back(), target_group, points)) {
				r.emplace_back(x);
			}
		}
		for (auto x : gen(r.back(), seq[0], {})) {
			r.emplace_back(x);
		}
		r.emplace_back(0);
		return r;
	}

	int64_t evaluate(const vector<int>& r) {
		int64_t s = 0;
		int prev = 0;
		for (int next : r) {
			s += get_dist(prev, next);
			prev = next;
		}
		return s;
	}

	void run() {
		int64_t min_score = 1LL << 60;
		vector<int> ans;

		while (!classify()) {
			;
		}

		vector<int> seq(M+1);
		iota(seq.begin(), seq.end(), 0);
		seq[M] = g[0];
		do {
			if (seq[0] == g[0]) {
				vector<int> r = gen(seq);
				int64_t score = evaluate(r);
				if (score < min_score) {
					min_score = score;
					ans = r;
				}
			}
		} while (next_permutation(seq.begin(), seq.begin() + M));

		output(ans);
	}
};

int main(int argc, char* argv[]) {
#if DEBUG
	freopen("in.txt", "r", stdin);
#endif
	Solver solver;
	solver.input();
	solver.prepare();
	solver.run();
}
0