結果
問題 | No.5007 Steiner Space Travel |
ユーザー |
|
提出日時 | 2022-07-30 15:40:46 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2 ms / 1,000 ms |
コード長 | 7,335 bytes |
コンパイル時間 | 3,948 ms |
実行使用メモリ | 6,952 KB |
スコア | 6,951,051 |
最終ジャッジ日時 | 2022-07-30 15:40:52 |
合計ジャッジ時間 | 5,780 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge15 |
純コード判定しない問題か言語 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 30 |
ソースコード
#pragma GCC target("avx2")#pragma GCC optimize("O3")#pragma GCC optimize("unroll-loops")#include <bits/stdc++.h>//#include <atcoder/all>using namespace std;//using namespace atcoder;template <class T>T sum(vector<T>& array) {return accumulate(array.begin(), array.end(), (T)0);}template <class T>int index(vector<T>& data, T element) {return distance(data.begin(), find(data.begin(),data.end(),element));}template <class T>int contain(vector<T>& data, T element) {return !(index(data, element) == (int)data.size());}struct Randomizer {mt19937_64 engine;uniform_int_distribution<> dist = uniform_int_distribution<>(0, INT_MAX);Randomizer() {random_device seed_gen;engine = mt19937_64(seed_gen());}Randomizer(int seed) {engine = mt19937_64(seed);}double uniform(double l, double r) {assert(l <= r);return l + (r-l)*dist(engine)/INT_MAX;}int randrange(int l, int r) {assert(l < r);return l + dist(engine)%(r-l);}template <class T>T choice(vector<T>& data) {return data.at(randrange(0, data.size()));}vector<int> sample(int l, int r, int num) {assert(0 < num && num <= r - l);vector<int> ret;while ((int)ret.size() < num) {int x = randrange(l, r);if (!contain(ret, x)) {ret.push_back(x);}}sort(ret.begin(), ret.end());return ret;}};struct Timer {timespec start;Randomizer randomizer;Timer() {}Timer(int seed) {randomizer = Randomizer(seed);}void begin() {clock_gettime(CLOCK_REALTIME, &start);}double stopwatch() {timespec end;clock_gettime(CLOCK_REALTIME, &end);double sec = end.tv_sec - start.tv_sec;double nsec = end.tv_nsec - start.tv_nsec;return sec + nsec/1000000000;}bool scheduler(double delta, double time_limit, double t0, double t1) {assert(0.0 < time_limit && 0.0 <= t1 && t1 <= t0);if (0.0 <= delta) {return true;} else {double ratio = stopwatch() / time_limit;double t = pow(t0, 1.0-ratio) * pow(t1, ratio);return randomizer.uniform(0.0, 1.0) < pow(2.0, delta/t);}}};vector<int> tsp_solver(vector<vector<int>> cost_matrix) {// n を始点および終点とするTSPの厳密解を求める.int n = cost_matrix.size() - 1;int s = n;int inf = 1 << 30;// dpvector<vector<int>> dp(n, vector<int>(1<<n,inf));for (int i = 0; i < n; i++) {dp[i][1<<i] = cost_matrix[s][i];}for (int mask = 1; mask < 1<<n; mask++) {for (int i = 0; i < n; i++) {if ((mask>>i & 1) == 0) {continue;}for (int j = 0; j < n; j++) {if (mask>>j & 1) {continue;}dp[j][mask^(1<<j)] = min(dp[j][mask^(1<<j)], dp[i][mask]+cost_matrix[i][j]);}}}// 経路復元int last = 0;int cost = inf;for (int i = 0; i < n; i++) {if (dp[i].back() + cost_matrix[i][s] < cost) {last = i;cost = dp[i].back() + cost_matrix[i][s];}}vector<int> ret = {last};int mask = (1<<n) - 1;mask ^= 1 << last;while (mask) {int j = ret.back();for (int i = 0; i < n; i++) {if (mask>>i & 1 && dp[i][mask] + cost_matrix[i][j] == dp[j][mask^1<<j]) {ret.push_back(i);mask ^= 1 << i;break;}}assert(ret.back() != j);}ret.push_back(s);reverse(ret.begin(), ret.end());return ret;}const int alpha = 5;const double time_limit = 0.95;const int inf = 1 << 30;struct Solver {Timer timer;Randomizer randomizer;int n, m;vector<int> a, b;vector<vector<int>> groups;vector<int> c, d;Solver() {timer.begin();}void input() {cin >> n >> m;a = vector<int>(n);b = vector<int>(n);for (int i = 0; i < n; i++) {cin >> a[i] >> b[i];}}pair<int,int> get_center(vector<int>& group) {if (group.empty()) {int j = randomizer.randrange(0, n);return {a[j], b[j]};}int x = 0;int y = 0;for (int i : group) {x += a[i];y += b[i];}return {x/(int)group.size(), y/(int)group.size()};}void k_means() {groups = vector<vector<int>>(m);for (int i = 0; i < m; i++) {groups[i].push_back(i);}for (int i = m; i < n; i++) {groups[randomizer.randrange(0,m)].push_back(i);}while (true) {vector<pair<int,int>> centers(m);for (int i = 0; i < m; i++) {centers[i] = get_center(groups[i]);}vector<vector<int>> new_groups(m);for (int i = 0; i < n; i++) {int best = 0;int min_cost = inf;for (int j = 0; j < m; j++) {auto [x, y] = centers[j];int cost = (a[i]-x)*(a[i]-x) + (b[i]-y)*(b[i]-y);if (cost < min_cost) {best = j;min_cost = cost;}}new_groups[best].push_back(i);}if (groups == new_groups) {break;}groups = new_groups;}}void solve() {k_means();c = vector<int>(m);d = vector<int>(m);for (int i = 0; i < m; i++) {pair<int,int> p = get_center(groups[i]);c[i] = p.first;d[i] = p.second;}vector<vector<int>> cost_matrix(m, vector<int>(m));for (int i = 0; i < m; i++) {for (int j = 0; j < m; j++) {int dist = (c[i]-c[j])*(c[i]-c[j]) + (d[i]-d[j])*(d[i]-d[j]);cost_matrix[i][j] = dist;cost_matrix[j][i] = dist;}}vector<int> order = tsp_solver(cost_matrix);int start = -1;for (int i = 0; i < m; i++) {if (contain(groups[order[i]], 0)) {start = i;}}vector<int> new_order(m);for (int i = 0; i < m; i++) {new_order[i] = order[(start+i) % m];}order = new_order;for (int i = 0; i < m; i++) {cout << c[i] << ' ' << d[i] << '\n';}cout << 2*n + m + 1 << '\n';for (int i = 0; i < m; i++) {int station = order[i];for (int star : groups[station]) {cout << 1 << ' ' << star + 1 << '\n';cout << 2 << ' ' << station + 1 << '\n';}cout << 2 << ' ' << order[(i+1) % m] + 1 << '\n';}cout << 1 << ' ' << 1 << '\n';}};int main() {Solver solver;solver.input();solver.solve();return 0;}