結果

問題 No.5007 Steiner Space Travel
コンテスト
ユーザー んんん
提出日時 2022-07-30 16:35:17
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 953 ms / 1,000 ms
コード長 4,498 bytes
コンパイル時間 2,164 ms
実行使用メモリ 6,948 KB
スコア 6,308,715
最終ジャッジ日時 2022-07-30 16:35:55
合計ジャッジ時間 33,235 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge14
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
using namespace std;

int NODE_CNT, M;

const double TL = 0.95;

const double T0 = 10.0;
const double T1 = 0.5;

inline double GetTime() {
    timespec getTime;
    clock_gettime(CLOCK_MONOTONIC, &getTime);
    return (getTime.tv_sec + getTime.tv_nsec*1e-9);
}

uint32_t xor128() {
    static uint32_t x = 123456789;
    static uint32_t y = 362436069;
    static uint32_t z = 521288629;
    static uint32_t w = 88675123;
    uint32_t t;
 
    t = x ^ (x << 11);
    x = y; y = z; z = w;
    return w = (w ^ (w >> 19)) ^ (t ^ (t >> 8));
}
double nextDouble() {
    return (xor128() + 0.5) * (1.0 / 4294967296.0);
}

struct State {
    vector<int> path;
};

int X[109], Y[109];
int mX[8], mY[8];

vector<vector<pair<long long, int>>> dist_list;
bool used[109];

double distance(int i, int j) {
    return sqrt((X[i] - X[j])*(X[i] - X[j]) + (Y[i] - Y[j])*(Y[i] - Y[j]));
}

double calc_diff(const State &state, int i, int j) {
    double ret = 0;
    int toi = i == NODE_CNT-1 ? 0 : i+1;
    int toj = j == 0 ? NODE_CNT-1 : j-1;

    if (i == toj) return 1 << 29;

    ret -= 25*distance(state.path[i], state.path[toi])*distance(state.path[i], state.path[toi]);
    ret -= 25*distance(state.path[j], state.path[toj])*distance(state.path[j], state.path[toj]);
    ret += 25*distance(state.path[i], state.path[toj])*distance(state.path[i], state.path[toj]);
    ret += 25*distance(state.path[j], state.path[toi])*distance(state.path[j], state.path[toi]);

    return ret;
}

int dx[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
int dy[8] = {0, 1, 1, 1, 0, -1, -1, -1};

int main() {
    cin >> NODE_CNT >> M;
    for (int i = 0; i < NODE_CNT; i++) cin >> X[i] >> Y[i];
    for (int i = 0; i < M; i++) {
        mX[i] = 500 + 250*dx[i];
        mY[i] = 500 + 250*dy[i];
    }

    for (int i = 0; i < NODE_CNT; i++) {
        vector<pair<long long, int>> dist;
        for (int j = 0; j < NODE_CNT; j++) {
            if (i == j) continue;
            long long dist2 = (X[i] - X[j])*(X[i] - X[j]) + (Y[i] - Y[j])*(Y[i] - Y[j]);
            dist.emplace_back(dist2, j);
        }
        sort(dist.begin(), dist.end());
        dist_list.push_back(dist);
    }

    State state;

    double score = 0;
    int start_node = 0;
    int now_node = 0;
    used[now_node] = true;
    state.path.push_back(0);
    int cnt = 0;
    while (true) {
        cnt++;
        bool flag = true;
        for (int i = 0; i < NODE_CNT-1; i++) {
            double dis = dist_list[now_node][i].first;
            int node = dist_list[now_node][i].second;
            if (used[node]) continue;
            flag = false;
            used[node] = true;
            state.path.push_back(node);
            score += 25*dis;

            now_node = node;

            break;
        }
        if (flag) {
            int dis = distance(start_node, now_node);
            score += 25*dis*dis;

            break;
        }
    }

    double now_time = GetTime();
    double start_time = GetTime();
    int iter = 0;
    double T = T0;
    while (true) {
        iter++;
        if (iter % 10000 == 0) {
            now_time = GetTime();
            double t = (now_time - start_time) / TL;
            if (t > 1) break;
            T = pow(T0, 1 - t) * pow(T1, t);
        }

        int i = xor128() % NODE_CNT;
        int j = xor128() % NODE_CNT;
        
        if (i > j) swap(i, j);
        double diff_score = calc_diff(state, i, j);

        double prob = exp(-diff_score/T);
        if (prob > nextDouble()) {
            score += diff_score;
            int toi = i == NODE_CNT-1 ? 0 : i+1;
            int toj = j == 0 ? NODE_CNT-1 : j-1;

            int x = toi, y = toj;
            if (y - x > i + NODE_CNT - j) {
                x = j, y = i + NODE_CNT;
            }
            while (x < y) {
                swap(state.path[x < NODE_CNT ? x : x - NODE_CNT], state.path[y < NODE_CNT ? y : y - NODE_CNT]);
                x++, y--;
            }
        }
    }
    for (int i = 0; i < M; i++) cout << mX[i] << ' ' << mY[i] << endl;
    cout << NODE_CNT+1 << endl;
    int i0 = -1;
    for (int i = 0; i < NODE_CNT; i++) {
        if (state.path[i] == 0) i0 = i;
    }
    for (int i = 0; i < NODE_CNT+1; i++) {
        int ind = i + i0;
        cout << 1 << ' ' << state.path[ind < NODE_CNT ? ind : ind-NODE_CNT]+1 << endl;
    }

    // cout << score << endl;
    // cout << (int)(1e9 / (1000 + sqrt(score))) << endl;
    // cout << iter << endl;
    // cout << GetTime() - start_time << endl;
}
0