結果

問題 No.5007 Steiner Space Travel
ユーザー Spady_JPSpady_JP
提出日時 2022-07-30 15:32:14
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 902 ms / 1,000 ms
コード長 4,653 bytes
コンパイル時間 3,889 ms
実行使用メモリ 6,952 KB
スコア 5,599,360
最終ジャッジ日時 2022-07-30 15:32:49
合計ジャッジ時間 34,543 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge14
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 902 ms
6,948 KB
testcase_01 AC 901 ms
4,900 KB
testcase_02 AC 902 ms
4,904 KB
testcase_03 AC 901 ms
4,904 KB
testcase_04 AC 902 ms
4,904 KB
testcase_05 AC 902 ms
6,952 KB
testcase_06 AC 902 ms
4,904 KB
testcase_07 AC 902 ms
4,904 KB
testcase_08 AC 900 ms
4,900 KB
testcase_09 AC 901 ms
6,948 KB
testcase_10 AC 902 ms
6,952 KB
testcase_11 AC 901 ms
6,948 KB
testcase_12 AC 901 ms
4,900 KB
testcase_13 AC 901 ms
4,900 KB
testcase_14 AC 902 ms
4,904 KB
testcase_15 AC 902 ms
6,948 KB
testcase_16 AC 902 ms
6,948 KB
testcase_17 AC 901 ms
4,900 KB
testcase_18 AC 901 ms
6,948 KB
testcase_19 AC 902 ms
4,904 KB
testcase_20 AC 901 ms
4,904 KB
testcase_21 AC 901 ms
4,900 KB
testcase_22 AC 902 ms
4,904 KB
testcase_23 AC 902 ms
4,900 KB
testcase_24 AC 901 ms
4,900 KB
testcase_25 AC 901 ms
4,904 KB
testcase_26 AC 902 ms
4,900 KB
testcase_27 AC 902 ms
4,900 KB
testcase_28 AC 902 ms
4,904 KB
testcase_29 AC 901 ms
4,904 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#ifdef ONLINE_JUDGE
    #define NDEBUG 1
#endif
#include <bits/stdc++.h>
//ifブロックはインデントがいる
#if __has_include(<atcoder/all>)
    #include <atcoder/all>
    using namespace atcoder;
#endif
#define repp(i,l,r)for(long long i=(l);i<(r);i++)
#define rep(i,n) for (long long i = 0; i < (n); ++i)
#define per(i,n) for (long long i = (n); i >= 0; --i)
#define all(v) v.begin(), v.end()
const int INF = 1<<30;
const long long LINF = 1LL << 60;
const long long int MOD = 1000000007;
using namespace std;
using ll = long long;
using P = pair<int,int>;
using PLI = pair<long long,long long>;
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }

unsigned int randxor() {
    static unsigned int x = 123456789, y = 362436069, z = 521288629,
                        w = 88675123;
    unsigned int t;
    t = (x ^ (x << 11));
    x = y;
    y = z;
    z = w;
    return (w = (w ^ (w >> 19)) ^ (t ^ (t >> 8)));
}

int dist(int from, int to) {
    if (to == 0) return 0;
    if (to == from)
        return from;
    else
        return randxor() % (to - from) + from;
}

struct Timer {
   public:
    Timer() { restart(); }

    void restart() { m_start = std::chrono::steady_clock::now(); }

    auto elapsed() {
        std::chrono::steady_clock::time_point en =
            std::chrono::steady_clock::now();
        auto dur = en - m_start;
        return std::chrono::duration_cast<std::chrono::milliseconds>(dur)
            .count();
    }

   private:
    std::chrono::_V2::steady_clock::time_point m_start;
};

int pair_dist(P x,P y){
    return (x.first - y.first) * (x.first - y.first) + (x.second - y.second) * (x.second - y.second);
}

long long calc(vector<P> &points, vector<P> &station,vector<P> &out){//type, to
    int alpha = 5;
    long double d = 0;
    if(!(out.front() == out.back() and out.front() == pair(1,1))){
        return -LINF;
    }

    auto [type, to] = out.front();
    --to;
    for (int i = 1; i < out.size(); i++) {
        auto x = (type == 1) ? points[out[i - 1].second - 1] : station[out[i - 1].second - 1];
        auto y = (out[i].first == 1) ? points[out[i].second - 1] : station[out[i].second - 1];
        long double tmp = (x.first - y.first) * (x.first - y.first) + (x.second - y.second) * (x.second - y.second);
        if (out[i].first == 1 and type == 1) {//ともに惑星
            d += alpha * alpha * tmp;
        }else if(min(out[i].first,type) == 1){
            d += alpha * tmp;
        }else{
            d += tmp;
        }
        type = out[i].first;
        to = out[i].second -1 ;
    }
    return -d;
}

//ミョ(-ω- ?)
int main() {
    cin.tie(nullptr) ;
    ios::sync_with_stdio(false) ;

    Timer tm;
    int n, m;
    cin >> n >> m;
    vector<P> points(n);
    rep(i, n) { cin >> points[i].first >> points[i].second; }
    vector<P> station(m);
    rep(i, m) { station[i] = {dist(0, 1000), dist(0, 1000)};}

    vector<P> out;
    //rep(i, n) { out.push_back({1, i + 1}); }
    //rep(i, m) { out.push_back({2, i + 1}); };
    out.push_back({1, 1});
    vector<bool> traveled(n, false);
    traveled[0] = true;
    int pos = 0;
    rep(_,n){
        int best_to = 0;
        int best_d = INF;
        rep(i, n) {
            if(!traveled[i] && best_d > pair_dist(points[pos],points[i])){
                best_to = i;
                best_d = pair_dist(points[pos], points[i]);
            }
        }
        pos = best_to;
        out.push_back({1, best_to + 1});
        traveled[best_to] = true;
    }
    out.push_back({1, 1});

    auto pre_score = calc(points, station, out);
    double start_temp = 50, end_temp = 10;
    while (tm.elapsed() < 900) {
        int ds = dist(1, out.size() - 1);
        int dt = dist(1, out.size() - 1);

        swap(out[ds], out[dt]);
        auto new_score = calc(points, station, out);
        double temp = start_temp + (end_temp - start_temp) * (tm.elapsed()) / 900;

        double prob = exp((new_score-pre_score)/temp);
        if (new_score > pre_score || prob > (randxor()%INF)/(double)INF) { // 確率probで遷移する
            pre_score = new_score;  
        }else{
            swap(out[ds], out[dt]);
            cerr << "new_score : " << new_score << "\n";
        }
    }

    rep(i, m) { cout << station[i].first << " " << station[i].second << "\n"; }
    cout << out.size() << "\n";
    rep(i, out.size()) { cout << out[i].first << " " << out[i].second << "\n"; }

    cerr << "Judge Score : " << round(1e9 / (1000 + sqrtl(-pre_score))) << "\n";
    return 0;
}
0