結果
| 問題 |
No.5007 Steiner Space Travel
|
| コンテスト | |
| ユーザー |
 ococonomy1
|
| 提出日時 | 2023-04-28 18:55:53 |
| 言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
| 結果 |
RE
|
| 実行時間 | - |
| コード長 | 12,549 bytes |
| コンパイル時間 | 2,176 ms |
| コンパイル使用メモリ | 133,716 KB |
| 実行使用メモリ | 4,376 KB |
| スコア | 4,602,158 |
| 最終ジャッジ日時 | 2023-04-28 18:56:22 |
| 合計ジャッジ時間 | 27,016 ms |
|
ジャッジサーバーID （参考情報） |
judge15 / judge11 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 19 RE * 10 TLE * 1 |
コンパイルメッセージ
main.cpp: 関数 ‘void k_means(int)’ 内:
main.cpp:131:34: 警告: ‘minsoeji’ may be used uninitialized [-Wmaybe-uninitialized]
131 | wakusei[i].group = minsoeji;
main.cpp:123:34: 備考: ‘minsoeji’ はここで定義されています
123 | int minvalue = IINF, minsoeji;
| ^~~~~~~~
ソースコード
//#pragma GCC target("avx2")
//#pragma GCC optimize("O3")
//#pragma GCC optimize("unroll-loops")
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <cassert>
#include <cmath>
#include <tuple>
#include <queue>
#include <bitset>
using namespace std;
using lg = long long;
#define TEST clog << "TEST" << endl
#define IINF 2147483647
#define LLINF 9223372036854775807LL
#define AMARI 998244353
#define TEMOTO ((sizeof(long double) == 16) ? false : true)
#define TIME_LIMIT 950 * (TEMOTO ? 1 : 1000)
#define el '\n'
#define El '\n'
clock_t start;
//疑似乱数(XorShift)
unsigned long xor128(void) {
static unsigned long x = 123456789, y = 362436069, z = 521288629, w = 88675123;
unsigned long t = (x xor (x << 11));
x = y; y = z; z = w;
return (w = (w xor (w >> 19)) xor (t xor (t >> 8)));
}
int wakusei_num, station_num;
class planet {
public:
int x;
int y;
int num;
int group;
};
bool hikaku_rad(planet a, planet b) {
return (atan2(a.y - 500, a.x - 500) < atan2(b.y - 500, b.x - 500));
}
int distance(int x1, int y1, int x2, int y2) {
return ((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
}
int planet_distance(planet const& a, planet const& b) {
int ans = (a.x - b.x) * (a.x - b.x);
ans += (a.y - b.y) * (a.y - b.y);
return ans;
}
class space_station {
public:
int x;
int y;
int num;
};
int station_distance(space_station const& a, space_station const& b) {
int ans = (a.x - b.x) * (a.x - b.x);
ans += (a.y - b.y) * (a.y - b.y);
return ans;
}
int output_lines = 0;
vector<planet> wakusei(100);
vector<space_station> station(8);
vector<vector<pair<int, int>>> keiro(8);
vector<int> station_junban(8);
//wakusei_group[i] = {i番目のグループに属している惑星の添え字}
vector<vector<int>> wakusei_group(8);
//tyokuset[i] = {i番目のステーションに直接つながってる惑星の添え字}
vector<vector<int>> tyokusetu(8);
//グループgのa番目とb番目の距離を返す
int planet_distance_soeji(int g, int a, int b) {
return planet_distance(wakusei[wakusei_group[g][a]], wakusei[wakusei_group[g][b]]);
}
void get_wakusei(void){
for (int i = 0; i < wakusei_num; i++) {
cin >> wakusei[i].x >> wakusei[i].y;
wakusei[i].num = i;
}
}
void k_means(int k = 8) {
for (int i = 0; i < wakusei_num; i++) {
wakusei[i].group = i % k;
}
bool henkou = true;
vector<int> kosuu(8, 0), xsum(8, 0), ysum(8, 0),xave(8),yave(8);
int cnt = 0;
while (henkou) {
henkou = false;
//それぞれのグループの平均点を求める
for (int i = 0; i < wakusei_num; i++) {
kosuu[wakusei[i].group]++;
xsum[wakusei[i].group] += wakusei[i].x;
ysum[wakusei[i].group] += wakusei[i].y;
}
for (int i = 0; i < station_num; i++) {
if (kosuu[i]) {
xave[i] = xsum[i] / kosuu[i];
yave[i] = ysum[i] / kosuu[i];
}
}
//それぞれの点から、最も近いグループ重心を求める
for (int i = 0; i < wakusei_num; i++) {
int minvalue = IINF, minsoeji;
for (int j = 0; j < 8; j++) {
if (minvalue > (xave[j] - wakusei[i].x) * (xave[j] - wakusei[i].x) + (yave[j] - wakusei[i].y) * (yave[j] - wakusei[i].y)) {
minvalue = (xave[j] - wakusei[i].x) * (xave[j] - wakusei[i].x) + (yave[j] - wakusei[i].y) * (yave[j] - wakusei[i].y);
minsoeji = j;
}
}
if (wakusei[i].group != minsoeji) {
wakusei[i].group = minsoeji;
henkou = true;
}
}
cnt++;
}
clog << "k-means loop kaisuu is " << cnt << el;
for (int i = 0; i < 8; i++) {
station[i].x = xave[i];
station[i].y = yave[i];
station[i].num = i;
}
for (int i = 0; i < wakusei_num; i++) {
//clog << wakusei[i]
wakusei_group[wakusei[i].group].push_back(i);
}
return;
}
void station_junban_kettei(void) {
vector<int> v(7);
int cnt = 0;
for (int i = 0; i < 8; i++) {
if (wakusei[0].group == i) {
continue;
}
v[cnt] = i;
cnt++;
}
//for(int i = 0; i < 7; i++)
int mindistance = IINF;
vector<int> minv;
do {
//station[0] →station[v0]→station[v1] →...station[v7]→station[0]で行くことを考える
int temp = station_distance(station[0], station[v[0]]) + station_distance(station[0], station[v[6]]);
for (int i = 0; i < 6; i++) {
temp += station_distance(station[v[i]], station[v[i + 1]]);
}
if (temp < mindistance) {
mindistance = temp;
minv = v;
}
} while (next_permutation(v.begin(), v.end()));
station_junban[0] = wakusei[0].group;
for (int i = 1; i < 8; i++) {
station_junban[i] = minv[i - 1];
}
//for (int i = 0; i < 8; i++)clog << station_junban[i] << ' ';
return;
}
//k-meansに従ってグループごとに分けたやつから初期解の経路を作る
void make_keiro_first(void) {
bool temp = false;
for (int i = wakusei[0].group; !temp || i != wakusei[0].group; i++) {
vector<pair<double, int>> rad(wakusei_group[i].size());
for (int j = 0; j < wakusei_group[i].size(); j++) {
rad[j].first = atan2(wakusei[wakusei_group[i][j]].y - station[i].y, wakusei[wakusei_group[i][j]].x - station[i].x);
rad[j].second = wakusei_group[i][j];
}
sort(rad.begin(), rad.end());
//点1があるグループの時、惑星1から始めるよう調整する必要がある
if (i == wakusei[0].group) {
for (int j = 0; j < wakusei_group[i].size(); j++) {
if (rad[j].second == 0) {
vector<pair<double, int>> tempv(rad.size());
for (int k = 0; k < rad.size(); k++) {
tempv[k] = rad[(j + k) % rad.size()];
}
rad = tempv;
//clog << rad[0].second << el;
break;
}
}
}
tyokusetu[i].push_back(rad[0].second);
for (int j = 0; j < wakusei_group[i].size(); j++) {
//clog << i << ' ' << j << el;
//経路について、rad[0].second→rad[1].second→...といく
//ただし、途中でステーションを経由した方がスコア的に良ければそうする
keiro[i].push_back({ 1,rad[j].second });
//clog << i << ' ' << j << el;
if (j == rad.size() - 1)break;
if (distance(wakusei[rad[j].second].x, wakusei[rad[j].second].y, wakusei[rad[j + 1].second].x, wakusei[rad[j + 1].second].y) * 5
> distance(wakusei[rad[j].second].x, wakusei[rad[j].second].y, station[i].x, station[i].y)
+ distance(wakusei[rad[j + 1].second].x, wakusei[rad[j + 1].second].y, station[i].x, station[i].y)) {
//惑星→惑星と行くより途中でステーションを経由した方が良い場合
keiro[i].push_back({ 2,i });
tyokusetu[i].push_back(rad[j + 1].second);
tyokusetu[i].push_back(rad[j + 1].second);
}
else {
}
//clog << i << ' ' << j << El;
}
vector<int>::iterator it = unique(tyokusetu[i].begin(), tyokusetu[i].end());
tyokusetu[i].erase(it, tyokusetu[i].end());
if (i == 7)i -= 8;
temp = true;
}
}
//とりあえずシンプルな2-opt
//なんかバグってる
void keiro_2_opt(void) {
while (clock() - start < TIME_LIMIT) {
int group = xor128() % 8;
//2箇所交換するところをランダムに選ぶ
int r1 = xor128() % wakusei_group[group].size(),r2 = xor128() % wakusei_group[group].size();
if (r1 == r2)continue;
if (r1 > r2)swap(r1, r2);
if (r1 == 0 || r2 + 1 == wakusei_group[group].size())continue;
if (wakusei_group[group][r1 - 1] == 0)continue;
//以下、r1の方が小さいとする
//r1とr2をswapした場合のことを考える。この時、-(r1-1→r1)-(r2→r2+1) +(r1-1→r2)+(r1→r2+1)が距離の増減である
if (planet_distance_soeji(group,r1 - 1,r1) + planet_distance_soeji(group, r2 + 1, r2) > planet_distance_soeji(group,r1 - 1,r2) + planet_distance_soeji(group,r1,r2 + 1)) {
//この時、変更後の方が小さいから、変更したい
//r1からr2までの順番を逆順にする
vector<pair<int,int>> temp;
for (int i = 0; i < keiro[group].size(); i++)clog << keiro[group][i].second << ' ';
clog << el;
for (int i = r1; i <= r2; i++)temp.push_back(keiro[group][i]);
for (int i = r2; i >= r1; i--)keiro[group][i] = temp[r2 - i];
for (int i = 0; i < keiro[group].size(); i++)clog << keiro[group][i].second << ' ';
clog << el;
break;
}
}
}
//ステーションsを(dx,dy)方向に動かした時、スコアがどのくらい良くなるか
int station_move_score_diff(int s, int dx, int dy) {
int ans = 0;
//まず、他のステーションとの距離の差分を計算する
if (s == 0) {
ans -= station_distance(station[0], station[7]);
ans -= station_distance(station[0], station[1]);
ans += distance(station[s].x + dx, station[s].y + dy, station[7].x, station[7].y);
ans += distance(station[s].x + dx, station[s].y + dy, station[1].x, station[1].y);
}
else {
ans -= station_distance(station[s], station[s - 1]);
ans -= station_distance(station[s], station[(s + 1) % 8]);
ans += distance(station[s].x + dx, station[s].y + dy, station[s - 1].x, station[s - 1].y);
ans += distance(station[s].x + dx, station[s].y + dy, station[(s + 1) % 8].x, station[(s + 1) % 8].y);
}
//tyokusetuの要素との距離の差分を計算する
//こちらには5をかける
for (int i = 0; i < tyokusetu[s].size(); i++) {
ans -= 5 * distance(station[s].x, station[s].y, wakusei[tyokusetu[s][i]].x, wakusei[tyokusetu[s][i]].y);
ans += 5 * distance(station[s].x + dx, station[s].y + dy, wakusei[tyokusetu[s][i]].x, wakusei[tyokusetu[s][i]].y);
}
return ans;
}
void yakinamasi(void) {
while (clock() - start < TIME_LIMIT) {
int ugokasu_station = xor128() % 8;
//いつか焼きなましにするけど一旦は山登りで実装する
//(x,y) →(x + dx, y + dy)
int dx = xor128() % 11 - 5, dy = xor128() % 11 - 5;
if (station_move_score_diff(ugokasu_station, dx, dy) < 0) {
clog << dx << ' ' << dy << el;
station[ugokasu_station].x += dx;
station[ugokasu_station].y += dy;
}
}
}
void print_keiro(void) {
//まず出力行数を数える
int gyousuu = 1;
for (int i = 0; i < 8; i++) {
//雑にこうやってるが、多分微妙に違う(後で修正)
//↑普通にgyousuuの初期値さえ考えればこれで大丈夫だが
gyousuu += keiro[i].size() + 2;
}
cout << gyousuu << el;
for (int i = 0; i < 8; i++) {
if (i)cout << "2 " << station_junban[i] + 1 << el;
for (int j = 0; j < keiro[station_junban[i]].size(); j++) {
cout << keiro[station_junban[i]][j].first << ' ' << keiro[station_junban[i]][j].second + 1 << el;
}
cout << "2 " << station_junban[i] + 1 << el;
}
cout << "2 " << wakusei[0].group + 1 << el;
cout << "1 1" << el;
return;
}
void print_station(void) {
for (int i = 0; i < station_num; i++) {
cout << station[i].x << ' ' << station[i].y << el;
}
}
#define MULTI_TEST_CASE false
void solve(void) {
cin >> wakusei_num >> station_num;
get_wakusei();
start = clock();
k_means(8);
station_junban_kettei();
make_keiro_first();
//keiro_2_opt():
yakinamasi();
print_station();
print_keiro();
return;
}
void calc(void) {
return;
}
int main(void) {
cin.tie(nullptr);
ios::sync_with_stdio(false);
int t = 1;
if (MULTI_TEST_CASE)cin >> t;
while (t--) {
solve();
}
calc();
return 0;
}