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

• 問題: No.5007 Steiner Space Travel
• ユーザー: nrvft
• 提出日時: 2022-07-30 15:02:18
• 言語: C++17 (gcc 12.3.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 8 ms / 1,000 ms
• コード長: 7,969 bytes
• コンパイル時間: 3,438 ms
• 実行使用メモリ: 3,672 KB
• スコア: 6,963,762
• 最終ジャッジ日時: 2022-07-30 15:02:24
• 合計ジャッジ時間: 5,425 ms
• ジャッジサーバーID （参考情報）: judge10 / judge14

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	7 ms; 3,432 KB
testcase_01	AC	7 ms; 3,552 KB
testcase_02	AC	7 ms; 3,500 KB
testcase_03	AC	7 ms; 3,428 KB
testcase_04	AC	7 ms; 3,580 KB
testcase_05	AC	7 ms; 3,576 KB
testcase_06	AC	8 ms; 3,432 KB
testcase_07	AC	7 ms; 3,588 KB
testcase_08	AC	7 ms; 3,496 KB
testcase_09	AC	7 ms; 3,528 KB
testcase_10	AC	7 ms; 3,484 KB
testcase_11	AC	7 ms; 3,532 KB
testcase_12	AC	7 ms; 3,672 KB
testcase_13	AC	7 ms; 3,528 KB
testcase_14	AC	7 ms; 3,552 KB
testcase_15	AC	7 ms; 3,508 KB
testcase_16	AC	7 ms; 3,588 KB
testcase_17	AC	7 ms; 3,620 KB
testcase_18	AC	7 ms; 3,668 KB
testcase_19	AC	7 ms; 3,568 KB
testcase_20	AC	7 ms; 3,436 KB
testcase_21	AC	7 ms; 3,532 KB
testcase_22	AC	7 ms; 3,672 KB
testcase_23	AC	7 ms; 3,576 KB
testcase_24	AC	8 ms; 3,496 KB
testcase_25	AC	8 ms; 3,436 KB
testcase_26	AC	7 ms; 3,528 KB
testcase_27	AC	7 ms; 3,524 KB
testcase_28	AC	7 ms; 3,500 KB
testcase_29	AC	7 ms; 3,544 KB

コンパイルメッセージ

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

ソースコード

#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) {
            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);
    }

    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);
        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]);

            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();
}