結果
問題 | No.5007 Steiner Space Travel |
ユーザー |
![]() |
提出日時 | 2022-07-30 16:08:13 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 903 ms / 1,000 ms |
コード長 | 6,140 bytes |
コンパイル時間 | 3,087 ms |
実行使用メモリ | 3,640 KB |
スコア | 8,727,222 |
最終ジャッジ日時 | 2022-07-30 16:08:46 |
合計ジャッジ時間 | 31,821 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge15 |
純コード判定しない問題か言語 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 30 |
ソースコード
#include <bits/stdc++.h>using namespace std;#define rep(i, n) for (int i = 0; i < (int)(n); i++)#define ALL(v) (v).begin(), (v).end()using ll = long long;constexpr int MOD = 1000000007;constexpr int N = 100;constexpr int M = 8;constexpr ll A = 5;int a[N], b[N];ll dist[N + M][N + M];constexpr double TIMELIMIT = 0.9;struct XorShift {unsigned int x, y, z, w, t;XorShift(int seed) {mt19937 rnd(seed);x = rnd();y = rnd();z = rnd();w = rnd();t = 1;}int rand() {t = x ^ (x << 11);x = y;y = z;z = w;w = (w ^ (w >> 19)) ^ (t ^ (t >> 8));return w & 0x7fffffff;}} rnd(rand());struct Timer {chrono::system_clock::time_point start, now;Timer() {start = chrono::system_clock::now();}double getTime() {now = chrono::system_clock::now();return chrono::duration<double>(now - start).count();}};struct State {int c[M], d[M];int order_of_planets[N + 1];ll score;};using P = pair<vector<int>, ll>;ll dfs_calc(int from, int to) {int mn = dist[from][to];int mid = -1;for (int v = 0; v < N + M; v++) {if (dist[from][v] + dist[v][to] < mn) {mn = dist[from][v] + dist[v][to];mid = v;}}if (mid == -1) return dist[from][to];return dfs_calc(from, mid) + dfs_calc(mid, to);}vector<int> dfs_output(int from, int to) {int mn = dist[from][to];int mid = -1;for (int v = 0; v < N + M; v++) {if (dist[from][v] + dist[v][to] < mn) {mn = dist[from][v] + dist[v][to];mid = v;}}if (mid == -1) return vector<int>();auto l = dfs_output(from, mid);auto r = dfs_output(mid, to);l.emplace_back(mid);for (int v : r) {l.emplace_back(v);}return l;}void calc(State& state) {for (int i = 0; i < M; i++) {for (int j = 0; j < M; j++) {dist[i][j] = dist[j][i] =(state.c[i] - state.c[j]) * (state.c[i] - state.c[j]) +(state.d[i] - state.d[j]) * (state.d[i] - state.d[j]);}for (int j = 0; j < N; j++) {dist[i][j + M] = dist[j + M][i] =A * ((state.c[i] - a[j]) * (state.c[i] - a[j]) +(state.d[i] - b[j]) * (state.d[i] - b[j]));}}state.score = 0;rep(i, N) {state.score += dfs_calc(state.order_of_planets[i] + M,state.order_of_planets[i + 1] + M);}}void output(State& state) {for (int i = 0; i < M; i++) {for (int j = 0; j < M; j++) {dist[i][j] = dist[j][i] =(state.c[i] - state.c[j]) * (state.c[i] - state.c[j]) +(state.d[i] - state.d[j]) * (state.d[i] - state.d[j]);}for (int j = 0; j < N; j++) {dist[i][j + M] = dist[j + M][i] =A * ((state.c[i] - a[j]) * (state.c[i] - a[j]) +(state.d[i] - b[j]) * (state.d[i] - b[j]));}}vector<pair<int, int>> ans;rep(i, N) {ans.emplace_back(1, state.order_of_planets[i] + 1);auto vec = dfs_output(state.order_of_planets[i] + M,state.order_of_planets[i + 1] + M);for (int v : vec) {ans.emplace_back(1 + (v < M), v - M * (M <= v) + 1);}}ans.emplace_back(1, state.order_of_planets[N] + 1);rep(i, M) {cout << state.c[i] << " " << state.d[i] << endl;}cout << ans.size() << endl;for (auto p : ans) {cout << p.first << " " << p.second << endl;}}void init(State& state) {int idx = 0;for (int x = 200; x <= 800; x += 300) {for (int y = 200; y <= 800; y += 300) {if (x == 800 && y == 800) break;state.c[idx] = x, state.d[idx++] = y;}}bool visited[N] = {};int cur = 0;visited[cur] = true;state.order_of_planets[0] = 0;for (int i = 1; i < N; i++) {int mn = INT_MAX;int nxt = 0;rep(to, N) {if (visited[to]) continue;if (dist[cur + M][to + M] < mn) {mn = dist[cur + M][to + M];nxt = to;}}cur = nxt;visited[cur] = true;state.order_of_planets[i] = cur;}state.order_of_planets[N] = 0;calc(state);}void modify(State& state) {if (rnd.rand() % 2) {int idx = rnd.rand() % M;state.c[idx] = rnd.rand() % 1001;state.d[idx] = rnd.rand() % 1001;} else {swap(state.order_of_planets[rnd.rand() % (N - 1) + 1],state.order_of_planets[rnd.rand() % (N - 1) + 1]);}calc(state);}void solve(State& state) {int steps = 0;Timer tmr;double nowclock;double startclock = tmr.getTime();// double starttemp, endtemp;while (true) {nowclock = tmr.getTime();if (nowclock - startclock > TIMELIMIT) break;State newstate = state;modify(newstate);if (newstate.score < state.score) {cerr << newstate.score << endl;state = newstate;}/*double temp = starttemp + (endtemp - starttemp) *(nowclock - startclock) / TIMELIMIT;double prob = exp((newstate.score - state.score) / temp);if (prob > (rnd.rand() % (int)1e9) / 1e9) {state = newstate;}*/steps++;}cerr << "score : " << state.score << endl;cerr << "steps : " << steps << endl;}void input() {int _N, _M;cin >> _N >> _M;rep(i, N) {cin >> a[i] >> b[i];}rep(i, N) {rep(j, N) {dist[i + M][j + M] =A * A *((a[i] - a[j]) * (a[i] - a[j]) + (b[i] - b[j]) * (b[i] - b[j]));}}}signed main() {input();State state;init(state);solve(state);output(state);return 0;}