結果
問題 | No.5007 Steiner Space Travel |
ユーザー | ococonomy1 |
提出日時 | 2023-04-28 18:55:53 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.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 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 980 ms
4,372 KB |
testcase_01 | AC | 963 ms
4,368 KB |
testcase_02 | RE | - |
testcase_03 | AC | 966 ms
4,368 KB |
testcase_04 | TLE | - |
testcase_05 | RE | - |
testcase_06 | AC | 986 ms
4,368 KB |
testcase_07 | RE | - |
testcase_08 | AC | 981 ms
4,368 KB |
testcase_09 | AC | 957 ms
4,368 KB |
testcase_10 | AC | 979 ms
4,368 KB |
testcase_11 | AC | 956 ms
4,368 KB |
testcase_12 | AC | 959 ms
4,372 KB |
testcase_13 | RE | - |
testcase_14 | AC | 960 ms
4,372 KB |
testcase_15 | RE | - |
testcase_16 | RE | - |
testcase_17 | AC | 984 ms
4,372 KB |
testcase_18 | AC | 957 ms
4,368 KB |
testcase_19 | AC | 979 ms
4,368 KB |
testcase_20 | RE | - |
testcase_21 | RE | - |
testcase_22 | AC | 984 ms
4,372 KB |
testcase_23 | AC | 956 ms
4,372 KB |
testcase_24 | AC | 957 ms
4,372 KB |
testcase_25 | AC | 957 ms
4,368 KB |
testcase_26 | AC | 957 ms
4,368 KB |
testcase_27 | RE | - |
testcase_28 | RE | - |
testcase_29 | AC | 962 ms
4,372 KB |
コンパイルメッセージ
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; }