結果

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

ソースコード

diff #
raw source code 

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

int NODE_CNT, M;

const double TL = 0.05;
const double TL2 = 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;
    vector<int> nearest;
};

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 distance(int xi, int yi, int xj, int yj) {
    return sqrt((xi - xj)*(xi - xj) + (yi - yj)*(yi - yj));
}

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;

    for (int i = 0; i < NODE_CNT; i++) {
        int ind = -1;
        double m = 1 << 29;
        for (int j = 0; j < M; j++) {
            int dist = distance(X[i], Y[i], mX[j], mY[j]);
            if (m > dist) {
                m = dist;
                ind = j;
            }
        }
        state.nearest.push_back(ind);
    }

    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;
    int ans_size =  NODE_CNT+1;
    vector<pair<int, int>> ans;
    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;
        ans.emplace_back(1, state.path[ind < NODE_CNT ? ind : ind-NODE_CNT]);
    }

    int addind = 0;
    vector<vector<pair<int, int>>> addans;
    for (int i = 0; i < NODE_CNT; i++) {
        int ind1 = i + i0 < NODE_CNT ? i+i0 : i+i0-NODE_CNT;
        int ind2 = ind1 + 1 < NODE_CNT ? ind1+1 : ind1+1-NODE_CNT;
        int n1 = state.path[ind1];
        int n2 = state.path[ind2];
        double dis1 = 25*distance(n1, n2)*distance(n1, n2);
        int m1 = state.nearest[n1];
        int m2 = state.nearest[n2];
        double dis2 = distance(mX[m1], mY[m1], mX[m2], mY[m2])*distance(mX[m1], mY[m1], mX[m2], mY[m2]);
        dis2 += 5*distance(X[n1], Y[n1], mX[m1], mY[m1])*distance(X[n1], Y[n1], mX[m1], mY[m1]);
        dis2 += 5*distance(X[n2], Y[n2], mX[m2], mY[m2])*distance(X[n2], Y[n2], mX[m2], mY[m2]);

        if (dis1 > dis2) {
            vector<pair<int, int>> a;
            a.emplace_back(ans[i]);
            a.emplace_back(2, m1);
            a.emplace_back(2, m2);
            addans.push_back(a);

            ans_size += 2;
            ans[i] = {0, addind};
            addind++;
            score -= dis1;
            score += dis2;
        }
    }

    cout << ans_size << endl;
    for (int i = 0; i < NODE_CNT+1; i++) {
        pair<int, int> p = ans[i];
        if (p.first == 0) {
            for (auto pp : addans[p.second]) cout << pp.first << ' ' << pp.second+1 << endl;
        } else {
            cout << p.first << ' ' << p.second+1 << endl;
        }
    }

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