#783214 (C++17) No.5007 Steiner Space Travel

提出ソース

結果

問題	No.5007 Steiner Space Travel
ユーザー	Dente
提出日時	2022-07-30 17:05:15
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	985 ms / 1,000 ms
コード長	5,979 bytes
コンパイル時間	1,899 ms
実行使用メモリ	6,952 KB
スコア	8,708,131
最終ジャッジ日時	2022-07-30 17:06:08
合計ジャッジ時間	34,410 ms
ジャッジサーバーID （参考情報）	judge13 / judge10
	純コード判定しない問題か言語

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	984 ms 4,904 KB
testcase_01	AC	983 ms 4,904 KB
testcase_02	AC	982 ms 6,948 KB
testcase_03	AC	983 ms 6,948 KB
testcase_04	AC	982 ms 6,948 KB
testcase_05	AC	982 ms 6,948 KB
testcase_06	AC	984 ms 4,908 KB
testcase_07	AC	984 ms 4,904 KB
testcase_08	AC	984 ms 4,904 KB
testcase_09	AC	982 ms 6,952 KB
testcase_10	AC	983 ms 4,900 KB
testcase_11	AC	982 ms 4,900 KB
testcase_12	AC	984 ms 6,948 KB
testcase_13	AC	983 ms 6,948 KB
testcase_14	AC	982 ms 6,948 KB
testcase_15	AC	984 ms 6,948 KB
testcase_16	AC	982 ms 4,900 KB
testcase_17	AC	983 ms 4,900 KB
testcase_18	AC	984 ms 4,904 KB
testcase_19	AC	983 ms 6,952 KB
testcase_20	AC	983 ms 6,952 KB
testcase_21	AC	983 ms 4,904 KB
testcase_22	AC	985 ms 4,900 KB
testcase_23	AC	981 ms 4,904 KB
testcase_24	AC	983 ms 6,952 KB
testcase_25	AC	982 ms 4,904 KB
testcase_26	AC	983 ms 6,952 KB
testcase_27	AC	983 ms 4,904 KB
testcase_28	AC	983 ms 4,900 KB
testcase_29	AC	982 ms 4,900 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#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.98;

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

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() % 200 - 100);
        if (state.c[idx] > 1000) state.c[idx] = 1000;
        if (state.c[idx] < 0) state.c[idx] = 0;
        state.d[idx] += (rnd.rand() % 200 - 100);
        if (state.d[idx] > 1000) state.d[idx] = 1000;
        if (state.d[idx] < 0) state.d[idx] = 0;
    } 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 = 0, startclock = tmr.getTime();
    while (true) {
        if (steps % 100 == 0) {
            nowclock = tmr.getTime();
            if (nowclock - startclock > TIMELIMIT) break;
        }
        State newstate = state;
        modify(newstate);
        if (newstate.score < state.score) {
            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;
}

yukicoder

結果

テストケース

ソースコード