結果

問題 No.5007 Steiner Space Travel
ユーザー DenteDente
提出日時 2022-07-30 16:18:16
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 984 ms / 1,000 ms
コード長 6,377 bytes
コンパイル時間 2,119 ms
実行使用メモリ 3,708 KB
スコア 8,708,062
最終ジャッジ日時 2022-07-30 16:18:50
合計ジャッジ時間 34,272 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge15
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 983 ms
3,576 KB
testcase_01 AC 983 ms
3,588 KB
testcase_02 AC 982 ms
3,476 KB
testcase_03 AC 983 ms
3,476 KB
testcase_04 AC 984 ms
3,540 KB
testcase_05 AC 983 ms
3,476 KB
testcase_06 AC 984 ms
3,620 KB
testcase_07 AC 982 ms
3,544 KB
testcase_08 AC 983 ms
3,616 KB
testcase_09 AC 984 ms
3,708 KB
testcase_10 AC 983 ms
3,620 KB
testcase_11 AC 983 ms
3,592 KB
testcase_12 AC 983 ms
3,580 KB
testcase_13 AC 984 ms
3,580 KB
testcase_14 AC 983 ms
3,544 KB
testcase_15 AC 982 ms
3,616 KB
testcase_16 AC 984 ms
3,636 KB
testcase_17 AC 982 ms
3,596 KB
testcase_18 AC 983 ms
3,588 KB
testcase_19 AC 982 ms
3,620 KB
testcase_20 AC 984 ms
3,544 KB
testcase_21 AC 983 ms
3,600 KB
testcase_22 AC 983 ms
3,544 KB
testcase_23 AC 983 ms
3,580 KB
testcase_24 AC 982 ms
3,464 KB
testcase_25 AC 984 ms
3,584 KB
testcase_26 AC 983 ms
3,632 KB
testcase_27 AC 984 ms
3,544 KB
testcase_28 AC 983 ms
3,472 KB
testcase_29 AC 983 ms
3,468 KB
権限があれば一括ダウンロードができます

ソースコード

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

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() % 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;
    double startclock = tmr.getTime();
    // double starttemp = 100, endtemp = 0;
    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;
        }
        /*
        double temp = starttemp + (endtemp - starttemp) *
                                      (nowclock - startclock) / TIMELIMIT;
        double prob = exp((state.score - newstate.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;
}
0