結果

問題 No.5007 Steiner Space Travel
コンテスト
ユーザー hotpepsi
提出日時 2023-04-29 01:05:43
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 12 ms / 1,000 ms
コード長 3,147 bytes
コンパイル時間 1,487 ms
コンパイル使用メモリ 116,384 KB
実行使用メモリ 4,372 KB
スコア 6,664,248
最終ジャッジ日時 2023-04-29 01:05:47
合計ジャッジ時間 3,709 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge11
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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() {

	}

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

	void 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> gen(const vector<int> &seq) {
		vector<int> r;
		for (int gg = 0; gg < M; ++gg) {
			int tg = seq[gg];
			for (int i = 0; i < N; ++i) {
				if (g[i] == tg) {
					r.emplace_back(i);
					r.emplace_back(N + tg);
				}
			}
			r.emplace_back(N + seq[gg + 1]);
		}
		r.emplace_back(0);
		return r;
	}

	int64_t evaluate(const vector<int>& r) {
		int64_t s = 0;
		int p = 0;
		for (int next : r) {
			int dx = x[next] - x[p], dy = y[next] - y[p];
			int64_t d = dx * dx + dy * dy;
			if (p < N) d *= 5;
			if (next < N) d *= 5;
			p = next;
			s += d;
		}
		return s;
	}

	void run() {
		int64_t min_score = 1LL << 60;
		vector<int> ans;
		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