結果

問題 No.5007 Steiner Space Travel
ユーザー longrun
提出日時 2022-07-30 17:38:28
言語 C++17(gcc12)
(gcc 12.3.0 + boost 1.87.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
純コード判定しない問題か言語
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0