結果
| 問題 |
No.5007 Steiner Space Travel
|
| コンテスト | |
| ユーザー |
 shibh308
|
| 提出日時 | 2022-07-30 17:56:59 |
| 言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 963 ms / 1,000 ms |
| コード長 | 13,583 bytes |
| コンパイル時間 | 4,944 ms |
| 実行使用メモリ | 6,952 KB |
| スコア | 8,893,705 |
| 最終ジャッジ日時 | 2022-07-30 17:57:52 |
| 合計ジャッジ時間 | 35,570 ms |
|
ジャッジサーバーID （参考情報） |
judge10 / judge15 |
| 純コード判定しない問題か言語 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 30 |
ソースコード
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
// #include "atcoder/all"
using namespace std;
using i64 = long long;
const i64 MOD = 1e9 + 7;
const i64 INF = i64(1e18);
template <typename T>
bool chmin(T& x, T y){
if(x > y){
x = y;
return true;
}
return false;
}
template <typename T>
bool chmax(T& x, T y){
if(x < y){
x = y;
return true;
}
return false;
}
uint32_t rnd(){
static uint32_t x = 123456789, y = 362436069, z = 521288629, w = 0;
uint32_t t = x ^ (x << 11);
x = y;
y = z;
z = w;
w = (w ^ (w >> 19)) ^ (t ^ (t >> 8));
return w;
}
double rnd_double(){
return 1.0 * rnd() / numeric_limits<uint32_t>::max();
}
// #define OPTIMIZE
namespace params{
void load_params(){
ifstream ifs("../params.txt");
assert(ifs.is_open());
}
}
// doc: https://shibh308.github.io/library/library/lib/functions/tsp.cpp.html
template<typename T>
vector<int> tsp(int n, vector<int> init, vector<vector<T>> dist, int iter_num){
// 始点=終点のTSP n <= 2 とかでバグりそうなので注意
vector<int> v = init;
vector<int> inv(n);
T now_dist = 0;
for(int i = 0; i < n; ++i){
inv[v[i]] = i;
now_dist += dist[v[i]][v[(i + 1) % n]];
}
// 前計算
vector<vector<pair<T,int>>> near_vertexes(n);
for(int i = 0; i < n; ++i){
for(int j = 0; j < n; ++j){
near_vertexes[i].emplace_back(dist[i][j], j);
}
sort(near_vertexes[i].begin(), near_vertexes[i].end());
}
auto dist_check = [&](){
auto di = dist[0][0];
for(int i = 0; i < n; ++i){
di += dist[v[i]][v[(i + 1) % n]];
}
assert(abs(now_dist - di) <= 1e-6);
};
auto update = [&](int i1, int i3){
int i2 = (i1 + 1) % n;
int i4 = (i3 + 1) % n;
if(i1 == i3 || i2 == i3 || i1 == i4 || i2 == i4)
return false;
if(dist[v[i1]][v[i2]] + dist[v[i3]][v[i4]] <= dist[v[i1]][v[i3]] + dist[v[i2]][v[i4]])
return false;
auto improve = (dist[v[i1]][v[i2]] + dist[v[i3]][v[i4]]) - (dist[v[i1]][v[i3]] + dist[v[i2]][v[i4]]);
now_dist -= improve;
int d1 = (i2 < i3 ? i3 - i2 : i3 + n - i2);
int d2 = (i4 < i1 ? i1 - i4 : i1 + n - i4);
if(d1 >= d2){
swap(i1, i3);
swap(i2, i4);
}
int st = i2;
int en = i2 < i3 ? i3 : i3 + n;
while(st < en){
inv[v[en % n]] = st % n;
inv[v[st % n]] = en % n;
swap(v[st % n], v[en % n]);
++st, --en;
}
// バグが怖い時用
// dist_check();
return true;
};
auto neighbors_search = [&](){
for(int i = 0; i < n; ++i){
int idx1 = i;
int idx2 = (i + 1) % n;
int v1 = v[idx1];
int v2 = v[idx2];
for(auto [d, v3] : near_vertexes[v1]){
if(v3 == v2)
break;
int idx3 = inv[v3];
if(update(idx1, idx3)){
return true;
}
}
for(auto [d, v4] : near_vertexes[v2]){
if(v4 == v1)
break;
int idx3 = (inv[v4] + n - 1) % n;
if(update(idx1, idx3)){
return true;
}
}
}
return false;
};
auto double_bridge = [&](){
vector<uint32_t> r{rnd() % n, rnd() % n, rnd() % n, rnd() % n};
sort(r.begin(), r.end());
if(r[0] == r[1] || r[1] == r[2] || r[2] == r[3]){
return true;
}
// (r[3] + 1, r[0]) => (r[2] + 1, r[3]) => (r[1] + 1, r[2]) => (r[0] + 1, r[1])
auto diff = dist[0][0];
diff -= dist[v[r[0]]][v[r[0] + 1]];
diff -= dist[v[r[1]]][v[r[1] + 1]];
diff -= dist[v[r[2]]][v[r[2] + 1]];
diff -= dist[v[r[3]]][v[(r[3] + 1) % n]];
diff += dist[v[r[0]]][v[r[2] + 1]];
diff += dist[v[r[3]]][v[r[1] + 1]];
diff += dist[v[r[2]]][v[r[0] + 1]];
diff += dist[v[r[1]]][v[(r[3] + 1) % n]];
now_dist += diff;
vector<int> nex;
nex.reserve(n);
for(int i = r[3] + 1; i < n; ++i)
nex.emplace_back(v[i]);
for(int i = 0; i <= r[0]; ++i)
nex.emplace_back(v[i]);
for(int i = r[2] + 1; i <= r[3]; ++i)
nex.emplace_back(v[i]);
for(int i = r[1] + 1; i <= r[2]; ++i)
nex.emplace_back(v[i]);
for(int i = r[0] + 1; i <= r[1]; ++i)
nex.emplace_back(v[i]);
v = move(nex);
return false;
};
auto best = make_pair(now_dist, v);
for(int i = 0; i < iter_num; ++i){
if(i){
while(double_bridge());
}
while(neighbors_search());
if(!chmin(best, make_pair(now_dist, v))){
tie(now_dist, v) = best;
}
}
for(int i = 0; i < n; ++i){
if(v[i] == 0){
vector<int> res;
for(int j = 0; j < n; ++j){
res.emplace_back(v[(i + j) % n]);
}
return res;
}
}
// return now_dist;
return v;
}
constexpr int n = 100;
constexpr int m = 8;
constexpr int alpha = 5;
array<i64, n> ax, ay;
void read_file(istream& ifs){
int a;
ifs >> a >> a;
// TODO: input
for(int i = 0; i < n; ++i){
ifs >> ax[i] >> ay[i];
}
}
clock_t st;
void solve(){
vector<vector<i64>> a_dist(n, vector<i64>(n));
vector<i64> bx(n), by(n);
auto raw_dis = [&](auto p1, auto q1, auto p2, auto q2){
i64 dx = (p1 == 0 ? ax[q1] : bx[q1]) - (p2 == 0 ? ax[q2] : bx[q2]);
i64 dy = (p1 == 0 ? ay[q1] : by[q1]) - (p2 == 0 ? ay[q2] : by[q2]);
return dx * dx + dy * dy;
};
auto dis = [&](auto p1, auto q1, auto p2, auto q2){
int alp = 1;
alp *= (p1 == 0 ? 5 : 1);
alp *= (p2 == 0 ? 5 : 1);
return raw_dis(p1, q1, p2, q2) * alp;
};
for(int i = 0; i < n; ++i){
for(int j = 0; j < n; ++j){
a_dist[i][j] = dis(0, i, 0, j);
}
}
vector<vector<int>> idxes_x(1001);
for(int i = 0; i < n; ++i){
idxes_x[ax[i]].emplace_back(i);
}
/*
vector<vector<i64>> points(1001, vector<i64>(1001, 0));
for(int i = 0; i < n; ++i){
for(int x = max(0LL, ax[i] - 300); x < min(ax[i] + 300, 100LL); ++x){
for(int y = max(0LL, ay[i] - 300); y < min(ay[i] + 300, 100LL); ++y){
int dx = x - ax[i];
int dy = y - ay[i];
if(dx * dx + dy * dy <= 100 * 100){
++points[x][y];
}
}
}
}
*/
bx = {200, 400, 600, 800};
by = {333, 333, 333, 333, 666, 666, 666, 666};
for(int i = 0; i < 8; ++i){
bx[i] = bx[i % 4];
}
/*
for(int j = 0; j < 8; ++j){
bool fl = false;
while(!fl && points[bx[j]][by[j]] <= 10){
bx[j] = 100 + rnd() % 800;
by[j] = 100 + rnd() % 800;
fl = true;
for(int i = 0; i < j; ++i){
int dx = bx[i] - bx[j];
int dy = by[i] - by[j];
if(sqrt(dx * dx + dy * dy) <= 300){
fl = false;
break;
}
}
}
}
*/
vector<int> v(100);
iota(v.begin(), v.end(), 0);
auto res = tsp(100, v, a_dist, 100);
res.emplace_back(0);
auto calc_ans = [&](){
vector<pair<int,int>> ans;
ans.emplace_back(0, 0);
i64 ds = 0;
for(int i = 0; i < n; ++i){
i64 d = dis(0, res[i], 0, res[i + 1]);
pair<i64,int> pp(d, -1);
for(int j = 0; j < m; ++j){
i64 d2 = dis(0, res[i], 1, j) + dis(1, j, 0, res[i + 1]);
chmin(pp, make_pair(d2, j));
}
ds += pp.first;
if(pp.second != -1){
ans.emplace_back(1, pp.second);
}
ans.emplace_back(0, res[i + 1]);
}
return make_pair(ans, ds);
};
auto calc_ans_light = [&](){
i64 ds = 0;
for(int i = 0; i < n; ++i){
i64 d = dis(0, res[i], 0, res[i + 1]);
pair<i64,int> pp(d, -1);
for(int j = 0; j < m; ++j){
i64 d2 = dis(0, res[i], 1, j) + dis(1, j, 0, res[i + 1]);
chmin(pp, make_pair(d2, j));
}
ds += pp.first;
}
return ds;
};
auto calc_sc = [&](i64 dist){
return round(1000000000 / (1000 + sqrt(dist)));
};
auto best = calc_ans_light();
auto best_b = make_pair(bx, by);
bool fl = true;
int itr = 0;
constexpr double start_temp = 1;//100000;
constexpr double end_temp = 1e-6;
constexpr double end_time = 0.92;
double per = 0.0;
bool upd = true;
while(fl){
// cout << per << endl;
for(int _ = 0; _ < 100; ++_){
double new_per = double(clock() - st) / CLOCKS_PER_SEC / end_time;
if(new_per >= 1.0){
fl = false;
break;
}
if(itr && itr % 3000 == 0 && upd){
// if(per < 0.3 && new_per >= 0.3){
// cout << new_per << ": " << "TSP ";
vector<vector<i64>> dist(n, vector<i64>(n));
for(int i = 0; i < n; ++i){
for(int j = 0; j < n; ++j){
dist[i][j] = dis(0, i, 0, j);
for(int k = 0; k < 8; ++k){
chmin(dist[i][j], dis(0, i, 1, k) + dis(1, k, 0, j));
}
}
}
res = tsp(n, res, dist, 50);
res.emplace_back(0);
// cout << best << " -> ";
best = calc_ans_light();
// cout << best << endl;
upd = false;
}
// per = new_per;
++itr;
int idx = rnd() & 7;
int px = bx[idx];
int py = by[idx];
int dx, dy;
int ty = 0;
if(rnd() % 4){
if(new_per >= 0.5){
dx = rnd() % 12 - 6;
dy = rnd() % 12 - 6;
}
else if(new_per >= 0.2){
dx = rnd() % 50 - 25;
dy = rnd() % 50 - 25;
}
else if(new_per >= 0.15){
dx = rnd() % 100 - 50;
dy = rnd() % 100 - 50;
}
else{
dx = rnd() % 300 - 150;
dy = rnd() % 300 - 150;
}
if(dx == 0 && dy == 0){
continue;
}
bx[idx] += dx;
by[idx] += dy;
}
else if(rnd() % 10 == 0){
int po = 0;
for(int i = 0; i < n; ++i){
if(dis(0, res[i], 0, res[i + 1]) > dis(0, res[i], 1, idx) + dis(1, idx, 0, res[i + 1])){
po = i;
break;
}
}
double dp = 0.5 + 0.5 * rnd_double();
int nx = ax[res[po]] + dp * (px - ax[res[po]]);
int ny = ay[res[po]] + dp * (py - ay[res[po]]);
bx[idx] = nx;
by[idx] = ny;
ty = 1;
}
else{
dx = rnd() % 600 - 300;
dy = rnd() % 600 - 300;
bx[idx] += dx;
by[idx] += dy;
ty = 2;
}
auto now = calc_ans_light();
auto diff = best - now;
/*
if(ty == 1){
cout << px << " " << py << " " << bx[idx] << " " << by[idx] << endl;
cout << diff << endl;
}
*/
// cout << diff << " " << temp << " : " << exp(diff / temp) << endl;
// if(exp(diff / temp) >= rnd_double()){
if(diff >= 0){
/*
if(ty != 1){
cout << new_per << ": " << dx << " " << dy << " " << best << " -> " << now << endl;
}
else{
cout << new_per << ": mov " << best << " -> " << now << endl;
}
*/
// cout << points[bx[idx]][by[idx]] << endl;
best = now;
// cout << calc_sc(best) << " " << ty << endl;
best_b = make_pair(bx, by);
upd = true;
}
else{
bx[idx] = px;
by[idx] = py;
}
}
}
// cout << itr << endl;
tie(bx, by) = best_b;
auto ans = calc_ans().first;
#ifdef HAND
cout << calc_sc(best) << endl;
cout << itr << endl;
#else
for(int i = 0; i < m; ++i){
cout << bx[i] << " " << by[i] << endl;
}
cout << ans.size() << endl;
for(int i = 0; i < ans.size(); ++i){
cout << ans[i].first + 1 << " " << ans[i].second + 1 << endl;
}
#endif
}
signed main(){
st = clock();
#ifdef OPTIMIZE
params::load_params();
#endif
#ifndef HAND
read_file(cin);
#else
ifstream ifs("./tools/in/0000.txt");
assert(ifs.is_open());
read_file(ifs);
#endif
solve();
}