結果

問題 No.5007 Steiner Space Travel
ユーザー Dente
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0