結果

問題 No.5007 Steiner Space Travel
ユーザー lud404Qe8lItbFmlud404Qe8lItbFm
提出日時 2023-04-26 05:18:33
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 904 ms / 1,000 ms
コード長 6,769 bytes
コンパイル時間 6,848 ms
コンパイル使用メモリ 270,796 KB
実行使用メモリ 4,376 KB
スコア 6,170,860
最終ジャッジ日時 2023-04-26 05:19:11
合計ジャッジ時間 36,614 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge14
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

diff # 

#if !__INCLUDE_LEVEL__

#include __FILE__
// 0以上UINT_MAX(0xffffffff)以下の乱数を整数で返す(xorshift)
static uint32_t random_xor() {
    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));
}

// 0以上1未満の乱数を実数で返す
static double random01() {
    return (random_xor() + 0.5) * (1.0 / UINT_MAX);
}
ll Euclid2d(ll x1, ll x2, ll y1, ll y2) {
    return (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2);
};
int main() {
    int N, M;
    cin >> N >> M;
    vector Planet(N, vector<int>(2));
    REP(i, N) {
        cin >> Planet[i][0] >> Planet[i][1];
    }
    vector<int> Cluster(N);

    random_device seed_gen;
    mt19937_64 rnd(seed_gen());
    uniform_int_distribution<int> Clu_N(0, M - 1);

    vector Center(M, vector<int>(2));
    REP(i, N) {
        Cluster[i] = Clu_N(rnd);
    }
    auto start_clock = system_clock::now();
    const static double START_TEMP = 1500;  // 開始時の温度
    const static double END_TEMP = 100;     // 終了時の温度
    const static double END_TIME = 0.9;     // 終了時間(秒)
    double time = 0.0;                      // 経過時間(秒)
    do {
        vector<int> ClusterNum(M, 0);
        vector tmp_center(M, vector<int>(2));
        REP(i, N) {
            tmp_center[Cluster[i]][0] += Planet[i][0];
            tmp_center[Cluster[i]][1] += Planet[i][1];
            ClusterNum[Cluster[i]] += 1;
        }
        REP(m, M) {
            if (ClusterNum[m] == 0) continue;
            tmp_center[m][0] /= ClusterNum[m];
            tmp_center[m][1] /= ClusterNum[m];
        }
        ll total = 0;
        ll tmp_total = 0;
        auto tmp_cluster = Cluster;
        REP(i, N) {
            int c = Cluster[i];
            ll D = Euclid2d(Planet[i][0], tmp_center[c][0], Planet[i][1],
                            tmp_center[c][1]);
            total += D;
            REP(m, M) {
                ll dist = Euclid2d(Planet[i][0], tmp_center[m][0], Planet[i][1],
                                   tmp_center[m][1]);
                if (dist < D) {
                    D = dist;
                    c = m;
                }
            }
            tmp_total += D;
            tmp_cluster[i] = c;
        }

        const double progress_ratio =
            time / END_TIME;  // 進捗。開始時が0.0、終了時が1.0
        const double temp =
            START_TEMP + (END_TEMP - START_TEMP) * progress_ratio;

        const double probability =
            exp((double)(total - tmp_total) / temp);  // 焼きなまし法の遷移確率
        if (probability > random01()) {
            Center = tmp_center;
            Cluster = move(tmp_cluster);
        }

        time = (duration_cast<microseconds>(system_clock::now() - start_clock)
                    .count() *
                1e-6);

    } while (time < END_TIME);

    REP(m, M) {
        cout << Center[m][0] << " " << Center[m][1] << endl;
    }
    vector<pair<int, int>> Out;
    int start = 0;
    vector Cplanet(8, vector<int>(0));
    REP(i, N) {
        Cplanet[Cluster[i]].emplace_back(i);
        if (i == 0) start = Cluster[i];
    }
    Out.emplace_back(1, 1);
    Out.emplace_back(2, start + 1);
    REP(m, M) {
        int station = (m + start) % M;
        if (station == start) {
            REPE(j, 1, Cplanet[station].size() - 1) {
                Out.emplace_back(1, Cplanet[station][j] + 1);
                Out.emplace_back(2, station + 1);
            }
        } else {
            REP(j, Cplanet[station].size()) {
                Out.emplace_back(1, Cplanet[station][j] + 1);
                Out.emplace_back(2, station + 1);
            }
        }
        Out.emplace_back(2, (station + 1) % M + 1);
    }
    Out.emplace_back(1, 1);
    ll V = Out.size();
    cout << V << "\n";
    REP(v, V) {
        cout << Out[v].first << " " << Out[v].second << "\n";
    }
}

#else
#include <bits/stdc++.h>

#include <atcoder/all>
using namespace std;
using namespace chrono;
using namespace atcoder;
typedef long long ll;
typedef unsigned long long ull;
#define REP(i, n) for (ll i = 0; i < ll(n); i++)
#define RREP(i, n) for (ll i = (ll)(n - 1); i >= 0; i--)
#define REPE(i, l, n) for (ll i = l; i <= ll(n); i++)
#define RREPE(i, l, n) for (ll i = ll(n); i >= l; i--)
#define FORA(i, I) for (const auto &i : I)
#define ALL(v) v.begin(), v.end()
#define UQ(v) v.erase(unique(ALL(v)), v.end())
#define ACM(v) accumulate(ALL(v), 0LL)
#define C cin >>
#define P(str) cout << str << endl
#define PLL pair<ll, ll>
#define PDBL pair<double, double>
#define TULL tuple<ll, ll, ll>
#define VPLL vector<PLL>
#define VLL vector<ll>
#define VVLL vector<VLL>
#define VVVLL vector<VVLL>
#define VDBL vector<double>
#define VPDBL vector<PDBL>
#define DLL deque<ll>
#define INCANT cin.tie(nullptr), ios::sync_with_stdio(false)
#define INT(...)     \
    int __VA_ARGS__; \
    IN(__VA_ARGS__)
#define LL(...)     \
    ll __VA_ARGS__; \
    IN(__VA_ARGS__)
#define STR(...)        \
    string __VA_ARGS__; \
    IN(__VA_ARGS__)
#define CHR(...)      \
    char __VA_ARGS__; \
    IN(__VA_ARGS__)
#define DBL(...)        \
    double __VA_ARGS__; \
    IN(__VA_ARGS__)
#define VEC(type, name, size) \
    vector<type> name(size);  \
    IN(name)
#define VEC2(type, name1, name2, size)     \
    vector<type> name1(size), name2(size); \
    for (int i = 0; i < size; i++) IN(name1[i], name2[i])
#define VEC3(type, name1, name2, name3, size)           \
    vector<type> name1(size), name2(size), name3(size); \
    for (int i = 0; i < size; i++) IN(name1[i], name2[i], name3[i])
#define VV(type, name, h, w)                       \
    vector<vector<type>> name(h, vector<type>(w)); \
    IN(name)
template <typename T>
inline bool chmax(T &a, T b) {
    return ((a < b) ? (a = b, true) : (false));
}
template <typename T>
inline bool chmin(T &a, T b) {
    return ((a > b) ? (a = b, true) : (false));
}
int scan() {
    return getchar();
}
void scan(int &a) {
    cin >> a;
}
void scan(long long &a) {
    cin >> a;
}
void scan(char &a) {
    cin >> a;
}
void scan(double &a) {
    cin >> a;
}
void scan(string &a) {
    cin >> a;
}
template <class T, class S>
void scan(pair<T, S> &p) {
    scan(p.first), scan(p.second);
}
template <class T>
void scan(vector<T> &);
template <class T>
void scan(vector<T> &a) {
    for (auto &i : a) scan(i);
}
template <class T>
void scan(T &a) {
    cin >> a;
}
void IN() {
}
template <class Head, class... Tail>
void IN(Head &head, Tail &...tail) {
    scan(head);
    IN(tail...);
}
const long long INF = 1100000000000000000;
const double EPS = 1e-9;
#endif
0