結果

問題 No.5007 Steiner Space Travel
ユーザー longrunlongrun
提出日時 2022-07-30 17:38:28
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 19 ms / 1,000 ms
コード長 2,180 bytes
コンパイル時間 752 ms
実行使用メモリ 6,952 KB
スコア 22,514
最終ジャッジ日時 2022-07-30 17:38:53
合計ジャッジ時間 4,093 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge14
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

diff # 

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

#define rep(i, n) for (int i = 0; i < (int)(n); i++)

using namespace std;

int N, M;
int ALPHA = 5;
vector<pair<int, int>> position_list;  // [0 : N) ... planet, [N : N + M) ... station

int get_distance(int a, int b) {
    int alpha = 1;
    if (a < N) {
        alpha *= ALPHA;
    }
    if (b < N) {
        alpha *= ALPHA;
    }
    auto& p = position_list[a];
    auto& q = position_list[b];
    return alpha * (p.first - q.first) * (p.first - q.first) + (p.second - q.second) * (p.second - q.second);
}


int main() {
    cin >> N >> M;
    position_list.assign(N + M, make_pair(0, 0));
    rep (i, N) {
        cin >> position_list[i].first >> position_list[i].second;
    }

    position_list[N + 0] = make_pair(0, 0);
    position_list[N + 1] = make_pair(0, 500);
    position_list[N + 2] = make_pair(0, 1000);
    position_list[N + 3] = make_pair(500, 0);
    position_list[N + 4] = make_pair(500, 1000);
    position_list[N + 5] = make_pair(1000, 0);
    position_list[N + 6] = make_pair(1000, 500);
    position_list[N + 7] = make_pair(1000, 1000);

    size_t max_ans_size = 100'000;
    vector<int> ans;
    rep (i, N + M) {
        rep (j, N + M) {
            if (i != j) {
                ans.push_back(i);
                ans.push_back(j);
            }
        }
    }

    int v, w;
    int max_dist = -1;
    rep (i, N + M) {
        rep (j, N + M) {
            if (int d = get_distance(i, j); d > max_dist) {
                max_dist = d;
                v = i;
                w = j;
            }
        }
    }
    while (ans.size() < max_ans_size - 1) {
        if ((int)ans.size() % 2) {
            ans.push_back(v);
        } else {
            ans.push_back(w);
        }
    }

    ans.push_back(0);

    rep (i, M) {
        auto& [x, y] = position_list[N + i];
        cout << x << " " << y << "\n";
    }
    cout << (int)ans.size() << "\n";
    rep (i, (int)ans.size()) {
        int x = ans[i];
        if (x >= N) {
            cout << 2 << " " << x - N + 1 << "\n";
        } else {
            cout << 1 << " " << x + 1 << "\n";
        }
    }
    return 0;
}
0