結果
| 問題 |
No.5007 Steiner Space Travel
|
| コンテスト | |
| ユーザー |
 takumi152
|
| 提出日時 | 2022-07-30 16:53:09 |
| 言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 988 ms / 1,000 ms |
| コード長 | 15,474 bytes |
| コンパイル時間 | 3,281 ms |
| 実行使用メモリ | 6,952 KB |
| スコア | 8,581,811 |
| 最終ジャッジ日時 | 2022-07-30 16:53:45 |
| 合計ジャッジ時間 | 35,660 ms |
|
ジャッジサーバーID （参考情報） |
judge12 / judge13 |
| 純コード判定しない問題か言語 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 30 |
ソースコード
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target ("avx2")
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <utility>
#include <string>
#include <queue>
#include <stack>
#include <unordered_set>
#include <random>
#include <cmath>
#include <cassert>
#include <x86intrin.h>
struct xorshift64 {
unsigned long long int x = 88172645463325252ULL;
inline unsigned short nextUShort() {
x = x ^ (x << 7);
return x = x ^ (x >> 9);
}
inline unsigned int nextUShortMod(unsigned long long int mod) {
x = x ^ (x << 7);
x = x ^ (x >> 9);
return ((x & 0x0000ffffffffffff) * mod) >> 48;
}
inline unsigned int nextUInt() {
x = x ^ (x << 7);
return x = x ^ (x >> 9);
}
inline unsigned int nextUIntMod(unsigned long long int mod) {
x = x ^ (x << 7);
x = x ^ (x >> 9);
return ((x & 0x00000000ffffffff) * mod) >> 32;
}
inline unsigned long long int nextULL() {
x = x ^ (x << 7);
return x = x ^ (x >> 9);
}
inline double nextDouble() {
x = x ^ (x << 7);
x = x ^ (x >> 9);
return (double)x * 5.42101086242752217e-20;
}
};
struct timer {
double t = 0.0;
double lastStop = 0.0;
bool stopped = false;
timer() {
restart();
}
inline void restart() {
t = now();
stopped = false;
}
inline void start() {
if (stopped) {
t += now() - lastStop;
stopped = false;
}
}
inline void stop() {
if (!stopped) {
lastStop = now();
stopped = true;
}
}
inline double time() {
if (stopped) return lastStop - t;
else return now() - t;
}
inline double now() {
unsigned long long l, h;
__asm__ ("rdtsc" : "=a"(l), "=d"(h));
#ifdef LOCAL
return (double)(l | h << 32) * 2.857142857142857e-10; // 1 / 3.5e9, for local (Ryzen 9 3950X)
#else
// return (double)(l | h << 32) * 3.5714285714285715e-10; // 1 / 2.8e9, for AWS EC2 C3 (Xeon E5-2680 v2)
// return (double)(l | h << 32) * 3.4482758620689656e-10; // 1 / 2.9e9, for AWS EC2 C4 (Xeon E5-2666 v3)
// return (double)(l | h << 32) * 3.333333333333333e-10; // 1 / 3.0e9, for AWS EC2 C5 (Xeon Platinum 8124M / Xeon Platinum 8275CL)
return (double)(l | h << 32) * 4.3478260869565215e-10; // 1 / 2.3e9, for yukicoder judge
#endif
}
};
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
typedef pair<int, int> Pii;
const ll mod = 1000000007;
timer theTimer;
xorshift64 theRandom;
mt19937 theMersenne(1);
// hyper parameters
// enums
// structs
// constants
constexpr int planet_num = 100;
constexpr int station_num = 8;
constexpr int planet_cost_factor = 5;
// inputs
vector<Pii> planet_pos;
// outputs
vector<Pii> station_pos;
vector<Pii> route_info;
// internals
vector<vector<int> > planet_to_planet_cost;
vector<vector<int> > station_to_planet_cost;
vector<vector<int> > station_to_station_cost;
vector<int> planet_visit_order;
void receive_input() {
int _n, _m;
cin >> _n >> _m;
planet_pos = vector<Pii>(planet_num);
for (auto &planet: planet_pos) cin >> planet.first >> planet.second;
}
void init_planet_to_planet_cost() {
planet_to_planet_cost = vector<vector<int> >(planet_num, vector<int>(planet_num));
for (int i = 0; i < planet_num; i++) {
for (int j = i; j < planet_num; j++) {
planet_to_planet_cost[i][j] = planet_cost_factor * planet_cost_factor * ((planet_pos[i].first - planet_pos[j].first) * (planet_pos[i].first - planet_pos[j].first) + (planet_pos[i].second - planet_pos[j].second) * (planet_pos[i].second - planet_pos[j].second));
planet_to_planet_cost[j][i] = planet_to_planet_cost[i][j];
}
}
}
void init_station_to_planet_cost() {
station_to_planet_cost = vector<vector<int> >(station_num, vector<int>(planet_num));
for (int i = 0; i < station_num; i++) {
for (int j = 0; j < planet_num; j++) {
station_to_planet_cost[i][j] = planet_cost_factor * ((station_pos[i].first - planet_pos[j].first) * (station_pos[i].first - planet_pos[j].first) + (station_pos[i].second - planet_pos[j].second) * (station_pos[i].second - planet_pos[j].second));
}
}
}
void init_station_to_station_cost() {
station_to_station_cost = vector<vector<int> >(station_num, vector<int>(planet_num));
for (int i = 0; i < station_num; i++) {
for (int j = i; j < station_num; j++) {
station_to_station_cost[i][j] = ((station_pos[i].first - station_pos[j].first) * (station_pos[i].first - station_pos[j].first) + (station_pos[i].second - station_pos[j].second) * (station_pos[i].second - station_pos[j].second));
station_to_station_cost[j][i] = station_to_station_cost[i][j];
}
}
}
void init() {
station_pos = vector<Pii>(station_num);
for (int i = 0; i < station_num; i++) {
station_pos[i] = Pii(theRandom.nextUIntMod(801) + 100, theRandom.nextUIntMod(801) + 100);
}
{
vector<int> planet_cluster(planet_num);
for (int i = 0; i < planet_num; i++) planet_cluster[i] = theRandom.nextUIntMod(station_num);
vector<int> next_planet_cluster = planet_cluster;
int iter_count = 0;
do {
planet_cluster = next_planet_cluster;
vector<int> cluster_count(station_num);
vector<Pii> cluster_pos_sum(station_num);
for (int i = 0; i < planet_num; i++) {
cluster_count[planet_cluster[i]]++;
cluster_pos_sum[planet_cluster[i]].first += planet_pos[i].first;
cluster_pos_sum[planet_cluster[i]].second += planet_pos[i].second;
}
for (int i = 0; i < station_num; i++) {
if (cluster_count[i] > 0) {
station_pos[i] = Pii(cluster_pos_sum[i].first / cluster_count[i], cluster_pos_sum[i].second / cluster_count[i]);
}
}
for (int i = 0; i < planet_num; i++) {
int nearest_station = -1;
int nearest_distance = 1000000007;
for (int j = 0; j < station_num; j++) {
int dist = (planet_pos[i].first - station_pos[j].first) * (planet_pos[i].first - station_pos[j].first) + (planet_pos[i].second - station_pos[j].second) * (planet_pos[i].second - station_pos[j].second);
if (dist < nearest_distance) {
nearest_station = j;
nearest_distance = dist;
}
}
next_planet_cluster[i] = nearest_station;
}
iter_count++;
} while (planet_cluster != next_planet_cluster || iter_count < 100);
}
init_planet_to_planet_cost();
init_station_to_planet_cost();
init_station_to_station_cost();
planet_visit_order = vector<int>(planet_num + 1);
{
planet_visit_order[0] = 0;
planet_visit_order[planet_num] = 0;
int current_planet = 0;
vector<bool> visited(planet_num);
visited[0] = true;
for (int i = 1; i < planet_num; i++) {
int best_planet = -1;
int best_cost = 1000000007;
for (int j = 0; j < planet_num; j++) {
if (!visited[j] && planet_to_planet_cost[current_planet][j] < best_cost) {
best_planet = j;
best_cost = planet_to_planet_cost[current_planet][j];
}
}
planet_visit_order[i] = best_planet;
current_planet = best_planet;
visited[best_planet] = true;
}
}
}
vector<Pii> find_shortest_route(int planet_from, int planet_to) {
vector<bool> planet_visited(planet_num);
vector<bool> station_visited(station_num);
vector<Pii> planet_prev_entity(planet_num);
vector<Pii> station_prev_entity(station_num);
priority_queue<tuple<int, int, int, int, int>, vector<tuple<int, int, int, int, int> >, greater<tuple<int, int, int, int, int> > > que; // cost, entity_type, entity_id, prev_entity_type, prev_entity_id
que.emplace(0, 1, planet_from, 1, planet_from);
while (!que.empty()) {
auto [cost, entity_type, entity_id, prev_entity_type, prev_entity_id] = que.top();
que.pop();
if (entity_type == 1) { // planet
if (planet_visited[entity_id]) continue;
planet_visited[entity_id] = true;
planet_prev_entity[entity_id] = Pii(prev_entity_type, prev_entity_id);
if (entity_id == planet_to) {
cerr << setw(4) << planet_pos[planet_from].first << " " << setw(4) << planet_pos[planet_from].second << " " << setw(4) << planet_pos[planet_to].first << " " << setw(4) << planet_pos[planet_to].second << " " << setw(6) << cost << endl;
break;
}
for (int next_planet = 0; next_planet < planet_num; next_planet++) {
if (!planet_visited[next_planet]) {
que.emplace(cost + planet_to_planet_cost[entity_id][next_planet], 1, next_planet, entity_type, entity_id);
}
}
for (int next_station = 0; next_station < station_num; next_station++) {
if (!station_visited[next_station]) {
que.emplace(cost + station_to_planet_cost[next_station][entity_id], 2, next_station, entity_type, entity_id);
}
}
}
else if (entity_type == 2) { // station
if (station_visited[entity_id]) continue;
station_visited[entity_id] = true;
station_prev_entity[entity_id] = Pii(prev_entity_type, prev_entity_id);
for (int next_planet = 0; next_planet < planet_num; next_planet++) {
if (!planet_visited[next_planet]) {
que.emplace(cost + station_to_planet_cost[entity_id][next_planet], 1, next_planet, entity_type, entity_id);
}
}
for (int next_station = 0; next_station < station_num; next_station++) {
if (!station_visited[next_station]) {
que.emplace(cost + station_to_station_cost[entity_id][next_station], 2, next_station, entity_type, entity_id);
}
}
}
}
vector<Pii> route;
int current_entity_type = 1;
int current_entity_id = planet_to;
while (!(current_entity_type == 1 && current_entity_id == planet_from)) {
route.emplace_back(current_entity_type, current_entity_id);
if (current_entity_type == 1) { // planet
auto [prev_entity_type, prev_entity_id] = planet_prev_entity[current_entity_id];
current_entity_type = prev_entity_type;
current_entity_id = prev_entity_id;
}
else if (current_entity_type == 2) { // station
auto [prev_entity_type, prev_entity_id] = station_prev_entity[current_entity_id];
current_entity_type = prev_entity_type;
current_entity_id = prev_entity_id;
}
}
reverse(route.begin(), route.end());
return route;
}
void update_route_info() {
route_info.emplace_back(1, 0);
for (int i = 0; i < planet_num; i++) {
auto path = find_shortest_route(planet_visit_order[i], planet_visit_order[i + 1]);
for (auto &entity: path) route_info.push_back(entity);
}
}
void solve() {
vector<vector<int> > cost_from_to(planet_num + station_num, vector<int>(planet_num + station_num));
auto update_cost = [&]() {
for (int i = 0; i < planet_num + station_num; i++) {
for (int j = 0; j < planet_num + station_num; j++) {
if (i < planet_num && j < planet_num) cost_from_to[i][j] = planet_to_planet_cost[i][j];
else if (i < planet_num) cost_from_to[i][j] = station_to_planet_cost[j - planet_num][i];
else if (j < planet_num) cost_from_to[i][j] = station_to_planet_cost[i - planet_num][j];
else cost_from_to[i][j] = station_to_station_cost[i - planet_num][j - planet_num];
}
}
for (int k = 0; k < planet_num + station_num; k++) {
for (int i = 0; i < planet_num + station_num; i++) {
for (int j = 0; j < planet_num + station_num; j++) {
if (cost_from_to[i][k] + cost_from_to[k][j] < cost_from_to[i][j]) cost_from_to[i][j] = cost_from_to[i][k] + cost_from_to[k][j];
}
}
}
};
update_cost();
{
auto calc_score = [&]() {
int score = 0;
for (int i = 0; i < planet_num; i++) score += cost_from_to[planet_visit_order[i]][planet_visit_order[i+1]];
return score;
};
int score = calc_score();
int last_score = score;
int best_score = score;
const double base_temperature = 3e3;
const double target_temperature = 1e2;
// const double decay_rate = 4e-5;
double temperature = base_temperature;
double time_start = theTimer.time();
const double time_limit = 0.980;
int iter_count = 0;
while (theTimer.time() < time_limit) {
double roll = theRandom.nextDouble();
if (roll < 0.99) {
int p1 = theRandom.nextUIntMod(planet_num - 1) + 1;
int p2 = theRandom.nextUIntMod(planet_num - 1) + 1;
if (p1 == p2) continue;
swap(planet_visit_order[p1], planet_visit_order[p2]);
score = calc_score();
#ifdef DEBUG
if (iter_count % 1000 == 0) cerr << iter_count << " " << score << " " << last_score << " " << best_score << " " << temperature << " " << theTimer.time() << endl;
#endif
if (score <= last_score) {
last_score = score;
if (score < best_score) {
best_score = score;
}
}
else if (theRandom.nextDouble() < exp(double(last_score - score) / temperature)) { // accept
last_score = score;
}
else { // rollback
swap(planet_visit_order[p1], planet_visit_order[p2]);
score = last_score;
}
}
else if (roll < 1.00) {
int s = theRandom.nextUIntMod(station_num);
int dx = theRandom.nextUIntMod(201) - 100;
int dy = theRandom.nextUIntMod(201) - 100;
if (dx == 0 && dy == 0) continue;
if (!(0 <= station_pos[s].first + dx && station_pos[s].first + dx <= 1000) || !(0 <= station_pos[s].second + dy && station_pos[s].second + dy <= 1000)) continue;
station_pos[s].first += dx;
station_pos[s].second += dy;
init_station_to_planet_cost();
init_station_to_station_cost();
update_cost();
score = calc_score();
#ifdef DEBUG
if (iter_count % 1000 == 0) cerr << iter_count << " " << score << " " << last_score << " " << best_score << " " << temperature << " " << theTimer.time() << endl;
#endif
if (score <= last_score) {
last_score = score;
if (score < best_score) {
best_score = score;
}
}
else if (theRandom.nextDouble() < exp(double(last_score - score) / temperature)) { // accept
last_score = score;
}
else { // rollback
station_pos[s].first -= dx;
station_pos[s].second -= dy;
init_station_to_planet_cost();
init_station_to_station_cost();
update_cost();
score = last_score;
}
}
// temperature *= 1.0 - decay_rate;
temperature = exp(log(base_temperature) - ((log(base_temperature) - log(target_temperature)) * ((theTimer.time() - time_start) * (1.0 / (time_limit - time_start)))));
iter_count++;
}
cerr << "iter_count = " << iter_count << endl;
cerr << "score = " << score << endl;
cerr << "best_score = " << best_score << endl;
cerr << "temperature = " << temperature << endl;
}
update_route_info();
}
void output_ans() {
for (auto &station: station_pos) {
cout << station.first << " " << station.second << endl;
}
cout << route_info.size() << endl;
for (auto &route: route_info) {
cout << route.first << " " << route.second + 1 << endl;
}
}
int main(int argc, char *argv[]) {
cin.tie(0);
ios::sync_with_stdio(false);
receive_input();
init();
solve();
output_ans();
return 0;
}