#783023 (C++17) No.5007 Steiner Space Travel

提出ソース

結果

問題	No.5007 Steiner Space Travel
ユーザー	nrvft
提出日時	2022-07-30 15:44:27
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	7 ms / 1,000 ms
コード長	10,396 bytes
コンパイル時間	3,182 ms
実行使用メモリ	6,952 KB
スコア	7,751,107
最終ジャッジ日時	2022-07-30 15:44:32
合計ジャッジ時間	5,072 ms
ジャッジサーバーID （参考情報）	judge15 / judge11
	純コード判定しない問題か言語

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	6 ms 4,904 KB
testcase_01	AC	6 ms 4,904 KB
testcase_02	AC	6 ms 4,904 KB
testcase_03	AC	6 ms 6,952 KB
testcase_04	AC	6 ms 4,904 KB
testcase_05	AC	6 ms 4,900 KB
testcase_06	AC	6 ms 4,900 KB
testcase_07	AC	6 ms 4,900 KB
testcase_08	AC	6 ms 4,904 KB
testcase_09	AC	6 ms 4,900 KB
testcase_10	AC	6 ms 4,904 KB
testcase_11	AC	7 ms 6,948 KB
testcase_12	AC	6 ms 6,952 KB
testcase_13	AC	6 ms 4,900 KB
testcase_14	AC	6 ms 4,900 KB
testcase_15	AC	6 ms 4,900 KB
testcase_16	AC	6 ms 6,948 KB
testcase_17	AC	6 ms 6,948 KB
testcase_18	AC	6 ms 4,900 KB
testcase_19	AC	6 ms 4,904 KB
testcase_20	AC	6 ms 4,904 KB
testcase_21	AC	6 ms 4,900 KB
testcase_22	AC	6 ms 4,900 KB
testcase_23	AC	7 ms 4,904 KB
testcase_24	AC	6 ms 6,948 KB
testcase_25	AC	6 ms 4,900 KB
testcase_26	AC	6 ms 6,952 KB
testcase_27	AC	6 ms 6,948 KB
testcase_28	AC	6 ms 6,948 KB
testcase_29	AC	7 ms 4,900 KB

権限があれば一括ダウンロードができます

コンパイルメッセージ

main.cpp: メンバ関数 ‘void Solver::input()’ 内:
main.cpp:357:28: 警告: narrowing conversion of ‘i’ from ‘ll’ {aka ‘long long int’} to ‘int’ [-Wnarrowing]
  357 |             ss[i] = {0, 0, i, false};
      |                            ^

ソースコード

raw source code

#pragma region MACRO
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using vl = vector<ll>;
template <class T>
using vc = vector<T>;
template <class T>
using vvc = vector<vector<T>>;

#define eb emplace_back
#define all(x) (x).begin(), (x).end()
#define rep(i, n) for (ll i = 0; i < (n); i++)
#define repr(i, n) for (ll i = (n)-1; i >= 0; i--)
#define repe(i, l, r) for (ll i = (l); i < (r); i++)
#define reper(i, l, r) for (ll i = (r)-1; i >= (l); i--)
#define repa(i, n) for (auto &i : n)

template <class T1, class T2>
inline bool chmax(T1 &a, const T2 &b) {
    if (a < b) {
        a = b;
        return 1;
    }
    return 0;
}
template <class T1, class T2>
inline bool chmin(T1 &a, const T2 &b) {
    if (b < a) {
        a = b;
        return 1;
    }
    return 0;
}

struct init {
    init() {
        cin.tie(0);
        ios::sync_with_stdio(false);
        cout << fixed << setprecision(15);
        cerr << fixed << setprecision(15);
    }
} init_;

template <typename T, typename U>
ostream &operator<<(ostream &out, const pair<T, U> &a) { return out << a.first << ' ' << a.second; }
template <typename T>
ostream &operator<<(ostream &out, const vector<T> &a) {
    for (auto it = a.begin(); it != a.end();) {
        out << *it;
        if (++it != a.end()) out << ' ';
    }
    return out;
}
template <typename T, size_t N>
ostream &operator<<(ostream &out, const array<T, N> &a) {
    for (auto it = a.begin(); it != a.end();) {
        out << *it;
        if (++it != a.end()) out << ' ';
    }
    return out;
}
template <typename T>
ostream &operator<<(ostream &out, const set<T> &a) {
    for (auto it = a.begin(); it != a.end();) {
        out << *it;
        if (++it != a.end()) out << ' ';
    }
    return out;
}
template <typename T, typename U>
ostream &operator<<(ostream &out, const map<T, U> &a) {
    for (auto it = a.begin(); it != a.end();) {
        out << *it;
        if (++it != a.end()) out << '\n';
    }
    return out;
}

#ifdef DEBUG
template <class T, class N>
void verr(const vector<T> &a, const N &n) {
    rep(i, n) cerr << a[i] << " ";
    cerr << endl;
}
template <class T, class N, size_t AN>
void verr(const array<T, AN> &a, const N &n) {
    rep(i, n) cerr << a[i] << " ";
    cerr << endl;
}
ll dbgt = 1;
void err() { cerr << "passed " << dbgt++ << endl; }
template <class H, class... T>
void err(H &&h, T &&...t) {
    cerr << h << (sizeof...(t) ? " " : "\n") << flush;
    if (sizeof...(t) > 0) err(forward<T>(t)...);
}
#else
void err() {}
template <class H, class... T>
void err(H &&h, T &&...t) {}
template <class H, class... T>
void verr(H &&h, T &&...t) {}
#endif

const ll INF = 4e18;
const ld EPS = 1e-11;
const ld PI = acos(-1.0L);
// const ll MOD = 1e9 + 7;
const ll MOD = 998244353;
//--------------------------------------------------------------------------------//

inline uint32_t pcg32() {
    static uint64_t x = 0x0123456789012345u;
    unsigned count = (unsigned)(x >> 61);
    x *= 3;
    x ^= x >> 22;
    return (uint32_t)(x >> (22 + count));
}
#pragma endregion

// 時間を出力
chrono::system_clock::time_point startTime, endTime;

// 経過時間(ms) を取得
int get_diff_time() {
    return chrono::duration_cast<chrono::milliseconds>(chrono::system_clock::now() - startTime).count();
}

// [0, a)の整数乱数
inline int get_randint(int a) {
    return pcg32() % a;
}

// [0, 1]の乱数
inline double get_randdouble() {
    return pcg32() / (double)numeric_limits<uint32_t>::max();
}

// 固定パラメータ
constexpr int N = 100;
constexpr int M = 8;
constexpr int ALPHA = 5;
// ハイパーパラメータ ---------------------------------
int ZERO = 0;
double TIME_LIMIT = 950; // ms

enum hyper_param_idx {
    ZERO_ID,
};

struct Solver {
    struct point {
        int x, y, id;
        bool is_planet;
        point() {}
        point(int x, int y, int id, bool isplanet): x(x),y(y),id(id),is_planet(isplanet){}

        int get_distance(point p) const{
            int d = (x - p.x) * (x - p.x) + (y - p.y) * (y - p.y);
            if (p.is_planet and is_planet) {
                return ALPHA * ALPHA * d;
            }else if(p.is_planet or is_planet) {
                return ALPHA * d;
            }else{
                return d;
            }
        }

        int get_raw_distance(point p) {
            int d = (x - p.x) * (x - p.x) + (y - p.y) * (y - p.y);
            return d;
        }
    };
    array<point, N> ps;
    array<point, N> ss;
    array<int, N> labels;
    array<vc<int>, M> lps;
    vc<point> ans;

    Solver() {
    }

    void kmeans(){
        const int iter = 2000;
        
        rep(i, N) labels[i] = i % M;

        auto prelabels = labels;
        int counter = 0;
        array<int, M> pcounts;
        array<point, M> psums;
        while (counter < iter) {
            rep(i, M) {
                pcounts[i] = 0;
                psums[i].x = psums[i].y = 0;
            }

            rep(i, N) {
                int l = labels[i];
                pcounts[l]++;
                psums[l].x += ps[i].x, psums[l].y += ps[i].y;
            }
            rep(i, M) {
                if(pcounts[i] > 0) {
                    ss[i].x = psums[i].x / pcounts[i];
                    ss[i].y = psums[i].y / pcounts[i];
                }
            }
            rep(i, N) {
                int mind = 1e9;
                rep(j, M) {
                    if(chmin(mind, ps[i].get_raw_distance(ss[j]))) {
                        labels[i] = j;
                    }
                }
            }
            if (labels == prelabels)
                break;
            prelabels = labels;
        }

        rep(i, N) lps[labels[i]].eb(i);
    }

    // 先頭惑星から初めて宇宙ステーションを含む焼きなまし
    vc<point> sim(int li) {
        const auto &ls = lps[li];
        const auto rp = ss[li];
        vc<point> route;
        if (ls.size() == 0) return route;
        route.eb(ps[ls[0]]), route.eb(ps[ls[0]]);
        
        for(auto pi: ls) {
            if (pi == ls[0]) continue;
            const auto &p = ps[pi];
            int mind = 1e9, mini = -1, mintype = -1;
            rep(i, route.size() - 1) {
                int rd = p.get_distance(rp);
                int pred = route[i].get_distance(route[i + 1]);

                int sumd = 0;
                sumd = p.get_distance(route[i]) + p.get_distance(route[i + 1]);
                sumd -= pred;
                if (chmin(mind, sumd)) mini = i + 1, mintype = 0;

                if(route[i].is_planet) {
                    sumd = rp.get_distance(route[i]) + rd + p.get_distance(route[i + 1]);
                    sumd -= pred;
                    if (chmin(mind, sumd)) mini = i + 1, mintype = 1;
                }
                if(route[i + 1].is_planet) {
                    sumd = p.get_distance(route[i]) + rd + rp.get_distance(route[i + 1]);
                    sumd -= pred;
                    if (chmin(mind, sumd)) mini = i + 1, mintype = 2;
                }
                if(route[i].is_planet and route[i].is_planet) {
                    sumd = rp.get_distance(route[i]) + 2 * rd + rp.get_distance(route[i + 1]);
                    sumd -= pred;
                    if (chmin(mind, sumd)) mini = i + 1, mintype = 3;
                }
            }
            assert(mini != -1 and mintype != -1);
            vc<point> ins;
            if (mintype & 1) ins.eb(rp);
            ins.eb(p);
            if (mintype & 2) ins.eb(rp);
            route.insert(route.begin() + mini, ins.begin(), ins.end());
        }

        return route;
    }

    void sa(){
        int diff_time = get_diff_time();
        kmeans();
        // while (diff_time < TIME_LIMIT) {
        //     diff_time = get_diff_time();
        //     repr(i, N) {
        //                 }
        // }

        int rtst = labels[0];
        array<int, M - 1> sts;
        rep(i, M - 1) {
            sts[i] = (i >= rtst ? i + 1 : i);
        }
        // err("rtst", rtst);
        // err(sts);

        array<vc<point>, M> routes;
        rep(i, M) {
            routes[i] = sim(i);
        }

        int mind = 1e9;
        do {
            vc<point> res;
            // res.eb(ps[0]), res.eb(ss[rtst]);
            // for(auto pi: lps[rtst]) {
            //     if (pi == 0) continue;
            //     res.eb(ps[pi]), res.eb(ss[rtst]);
            // }

            // rep(i, M - 1) {
            //     int si = sts[i];
            //     res.eb(ss[si]);
            //     for(auto pi: lps[si]) {
            //         res.eb(ps[pi]), res.eb(ss[si]);
            //     }
            // }

            // res.eb(ss[rtst]), res.eb(ps[0]);

            res.insert(res.end(), routes[rtst].begin(), routes[rtst].end());
            res.eb(ss[rtst]);

            rep(i, M - 1) {
                int si = sts[i];
                res.eb(ss[si]);
                res.insert(res.end(), routes[si].begin(), routes[si].end());
                res.eb(ss[si]);
            }
            res.eb(ss[rtst]), res.eb(ps[0]);

            int sumd = 0;
            rep(i, res.size() - 1) {
                sumd += res[i].get_distance(res[i + 1]);
            }
            if(chmin(mind, sumd)) {
                ans = res;
            }
        } while (next_permutation(all(sts)));
    }

    void solve() {
        input();
        init();
        sa();
        output();
    }

    void input() {
        int n, m;
        cin >> n >> m;
        rep(i, N) {
            cin >> ps[i].x >> ps[i].y;
            ps[i].id = i;
            ps[i].is_planet = true;
        }
        rep(i, M) {
            ss[i] = {0, 0, i, false};
        }
    }

    void init(){

    }

    void output() {
        rep(i, M) {
            cout << ss[i].x << " " << ss[i].y << '\n';
        }
        // int n = 101;
        // cout << n << '\n';
        // rep(i, N) cout << 1 << " " << i + 1 << '\n';
        // cout << 1 << " " << 1 << '\n';
        cout << ans.size() << '\n';
        for (auto p : ans) {
            cout << (p.is_planet ? 1 : 2) << " " << p.id + 1 << '\n';
        }
    }
};

int main() {
    startTime = chrono::system_clock::now();
#ifdef TUNE
    // params
#endif
    Solver solver;
    solver.solve();
}

yukicoder

結果

テストケース

コンパイルメッセージ

ソースコード