結果
| 問題 | No.5007 Steiner Space Travel |
| ユーザー |
 fuppy_kyopro
|
| 提出日時 | 2022-07-30 19:16:52 |
| 言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
AC
|
| 実行時間 | 986 ms / 1,000 ms |
| コード長 | 18,656 bytes |
| コンパイル時間 | 4,321 ms |
| 実行使用メモリ | 6,952 KB |
| スコア | 8,989,959 |
| 最終ジャッジ日時 | 2022-07-30 19:17:29 |
| 合計ジャッジ時間 | 36,763 ms |
|
ジャッジサーバーID （参考情報） |
judge15 / judge11 |
| 純コード判定しない問題か言語 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 978 ms
4,416 KB |
| testcase_01 | AC | 933 ms
4,300 KB |
| testcase_02 | AC | 950 ms
4,512 KB |
| testcase_03 | AC | 953 ms
4,224 KB |
| testcase_04 | AC | 977 ms
4,512 KB |
| testcase_05 | AC | 963 ms
4,328 KB |
| testcase_06 | AC | 974 ms
4,428 KB |
| testcase_07 | AC | 954 ms
4,216 KB |
| testcase_08 | AC | 947 ms
4,556 KB |
| testcase_09 | AC | 949 ms
4,296 KB |
| testcase_10 | AC | 971 ms
4,364 KB |
| testcase_11 | AC | 968 ms
4,216 KB |
| testcase_12 | AC | 974 ms
4,288 KB |
| testcase_13 | AC | 958 ms
4,292 KB |
| testcase_14 | AC | 970 ms
4,288 KB |
| testcase_15 | AC | 958 ms
4,416 KB |
| testcase_16 | AC | 981 ms
4,428 KB |
| testcase_17 | AC | 938 ms
4,424 KB |
| testcase_18 | AC | 963 ms
4,512 KB |
| testcase_19 | AC | 979 ms
4,900 KB |
| testcase_20 | AC | 964 ms
4,428 KB |
| testcase_21 | AC | 982 ms
4,900 KB |
| testcase_22 | AC | 938 ms
4,220 KB |
| testcase_23 | AC | 938 ms
4,316 KB |
| testcase_24 | AC | 966 ms
4,420 KB |
| testcase_25 | AC | 936 ms
4,248 KB |
| testcase_26 | AC | 976 ms
4,296 KB |
| testcase_27 | AC | 931 ms
4,364 KB |
| testcase_28 | AC | 986 ms
4,248 KB |
| testcase_29 | AC | 962 ms
6,952 KB |
ソースコード
//*
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
//*/
#include <bits/stdc++.h>
// #include <atcoder/all>
using namespace std;
// using namespace atcoder;
// #define _GLIBCXX_DEBUG
#define DEBUG(x) cerr << #x << ": " << x << endl;
#define DEBUG_VEC(v) \
cerr << #v << ":"; \
for (int iiiiiiii = 0; iiiiiiii < v.size(); iiiiiiii++) \
cerr << " " << v[iiiiiiii]; \
cerr << endl;
#define DEBUG_MAT(v) \
cerr << #v << endl; \
for (int iv = 0; iv < v.size(); iv++) { \
for (int jv = 0; jv < v[iv].size(); jv++) { \
cerr << v[iv][jv] << " "; \
} \
cerr << endl; \
}
typedef long long ll;
// #define int ll
#define vi vector<int>
#define vl vector<ll>
#define vii vector<vector<int>>
#define vll vector<vector<ll>>
#define vs vector<string>
#define pii pair<int, int>
#define pis pair<int, string>
#define psi pair<string, int>
#define pll pair<ll, ll>
template <class S, class T>
pair<S, T> operator+(const pair<S, T> &s, const pair<S, T> &t) {
return pair<S, T>(s.first + t.first, s.second + t.second);
}
template <class S, class T>
pair<S, T> operator-(const pair<S, T> &s, const pair<S, T> &t) { return pair<S, T>(s.first - t.first, s.second - t.second); }
template <class S, class T>
ostream &operator<<(ostream &os, pair<S, T> p) {
os << "(" << p.first << ", " << p.second << ")";
return os;
}
#define X first
#define Y second
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep1(i, n) for (int i = 1; i <= (int)(n); i++)
#define rrep(i, n) for (int i = (int)(n)-1; i >= 0; i--)
#define rrep1(i, n) for (int i = (int)(n); i > 0; i--)
#define REP(i, a, b) for (int i = a; i < b; i++)
#define in(x, a, b) (a <= x && x < b)
#define all(c) c.begin(), c.end()
void YES(bool t = true) {
cout << (t ? "YES" : "NO") << endl;
}
void Yes(bool t = true) { cout << (t ? "Yes" : "No") << endl; }
void yes(bool t = true) { cout << (t ? "yes" : "no") << endl; }
void NO(bool t = true) { cout << (t ? "NO" : "YES") << endl; }
void No(bool t = true) { cout << (t ? "No" : "Yes") << endl; }
void no(bool t = true) { cout << (t ? "no" : "yes") << endl; }
template <class T>
bool chmax(T &a, const T &b) {
if (a < b) {
a = b;
return 1;
}
return 0;
}
template <class T>
bool chmin(T &a, const T &b) {
if (a > b) {
a = b;
return 1;
}
return 0;
}
#define UNIQUE(v) v.erase(std::unique(v.begin(), v.end()), v.end());
const ll inf = 1000000001;
const ll INF = (ll)1e18 + 1;
const long double pi = 3.1415926535897932384626433832795028841971L;
int popcount(ll t) { return __builtin_popcountll(t); }
// int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
// int dx2[8] = { 1,1,0,-1,-1,-1,0,1 }, dy2[8] = { 0,1,1,1,0,-1,-1,-1 };
vi dx = {0, 0, -1, 1}, dy = {-1, 1, 0, 0};
vi dx2 = {1, 1, 0, -1, -1, -1, 0, 1}, dy2 = {0, 1, 1, 1, 0, -1, -1, -1};
struct Setup_io {
Setup_io() {
ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cout << fixed << setprecision(25);
}
} setup_io;
const ll MOD = 1000000007;
// const ll MOD = 998244353;
// #define mp make_pair
//#define endl '\n'
struct dice {
mt19937 mt;
dice() : mt(chrono::steady_clock::now().time_since_epoch().count()) {}
// [0, x)の一様乱数
ll operator()(ll x) { return this->operator()(0, x); }
// [x, y)の一様乱数
ll operator()(ll x, ll y) {
uniform_int_distribution<ll> dist(x, y - 1);
return dist(mt);
}
vl operator()(int n, ll x, ll y) {
vl res(n);
for (int i = 0; i < n; i++)
res[i] = this->operator()(x, y);
return res;
}
} rnd;
constexpr int n = 100, m = 8;
constexpr int alpha = 5;
vector<pii> ab(n);
vector<pii> cd(m);
void input() {
int nn, mm;
cin >> nn >> mm;
rep(i, n) {
cin >> ab[i].first >> ab[i].second;
}
rep(i, m) {
int y = i / 3;
int x = i % 3;
cd[i] = pii(250 * (y + 1), 250 * (x + 1));
}
}
int calc_dist(pii xy1, pii xy2) {
pll dxy = xy1 - xy2;
return dxy.first * dxy.first + dxy.second * dxy.second;
}
int ori_hyou[n][n];
int hyou[n][n];
pii ori_inter[n][n];
pii inter[n][n];
pair<int, pii> find_min_inter(int i, int j) {
int hyo = calc_dist(ab[i], ab[j]) * alpha * alpha;
pii inte = pii(-1, -1);
rep(k, m) {
if (chmin(hyo, (calc_dist(ab[i], cd[k]) + calc_dist(cd[k], ab[j])) * alpha)) {
inte = pii(k, -1);
}
}
rep(k1, m) {
int temp = calc_dist(ab[i], cd[k1]) * alpha;
if (temp >= hyo) {
continue;
}
rep(k2, m) {
int add = calc_dist(cd[k1], cd[k2]) + calc_dist(cd[k2], ab[j]) * alpha;
if (chmin(hyo, temp + add)) {
inte = pii(k1, k2);
}
}
}
return {hyo, inte};
}
void fill_hyou() {
rep(i, n) {
rep(j, n) {
ori_hyou[i][j] = hyou[i][j];
ori_inter[i][j] = inter[i][j];
}
}
rep(i, n) {
REP(j, i, n) {
auto [hyo, inte] = find_min_inter(i, j);
hyou[i][j] = hyo;
inter[i][j] = inte;
hyou[j][i] = hyou[i][j];
inter[j][i] = inter[i][j];
if (inter[j][i].second != -1) {
swap(inter[j][i].first, inter[j][i].second);
}
}
}
}
int calc_score(const vi &dist) {
ll sum = 0;
rep(i, n) sum += dist[i];
return round(1e9 / (1000 + sqrt(sum)));
}
int two_opt(vector<int> &jun) {
fill_hyou();
static vector<int> dist(n);
rep(i, n) {
int s = jun[i], t = jun[(i + 1) % n];
dist[i] = hyou[s][t];
}
bool updated = true;
while (updated) {
updated = false;
for (int i = 1; i < n; i++) {
for (int j = i + 1; j < n; j++) {
int sub = 0, add = 0;
sub += hyou[jun[i - 1]][jun[i]];
add += hyou[jun[i - 1]][jun[j]];
sub += hyou[jun[j]][jun[(j + 1) % n]];
add += hyou[jun[i]][jun[(j + 1) % n]];
if (sub > add) {
reverse(jun.begin() + i, jun.begin() + j + 1);
reverse(dist.begin() + i, dist.begin() + j);
dist[i - 1] = hyou[jun[i - 1]][jun[i]];
dist[j] = hyou[jun[j]][jun[(j + 1) % n]];
updated = true;
}
}
}
}
return calc_score(dist);
}
int three_opt(vector<int> &jun) {
fill_hyou();
bool updated = true;
while (updated) {
updated = false;
rep(i, n) {
REP(j, i + 1, n) {
REP(k, j + 1, n) {
int sub = 0;
int A = jun[i], B = jun[i + 1], C = jun[j], D = jun[j + 1], E = jun[k], F = jun[(k + 1) % n];
sub += hyou[A][B];
sub += hyou[C][D];
sub += hyou[E][F];
int best_add = inf;
int best_type = -1;
{
int add = 0;
add += hyou[A][C];
add += hyou[B][E];
add += hyou[D][F];
if (chmin(best_add, add)) {
best_type = 0;
}
}
{
int add = 0;
add += hyou[A][D];
add += hyou[E][B];
add += hyou[C][F];
if (chmin(best_add, add)) {
best_type = 1;
}
}
{
int add = 0;
add += hyou[A][D];
add += hyou[E][C];
add += hyou[B][F];
if (chmin(best_add, add)) {
best_type = 2;
}
}
{
int add = 0;
add += hyou[A][E];
add += hyou[D][B];
add += hyou[C][F];
if (chmin(best_add, add)) {
best_type = 3;
}
}
if (best_add >= sub) {
continue;
}
updated = true;
assert(best_type != -1);
static vi new_jun;
new_jun.clear();
if (best_type == 0) {
rep(idx, i + 1) {
new_jun.push_back(jun[idx]);
}
for (int idx = j; idx >= i + 1; idx--) {
new_jun.push_back(jun[idx]);
}
for (int idx = k; idx >= j + 1; idx--) {
new_jun.push_back(jun[idx]);
}
REP(idx, k + 1, n) {
new_jun.push_back(jun[idx]);
}
} else if (best_type == 1) {
rep(idx, i + 1) {
new_jun.push_back(jun[idx]);
}
REP(idx, j + 1, k + 1) {
new_jun.push_back(jun[idx]);
}
REP(idx, i + 1, j + 1) {
new_jun.push_back(jun[idx]);
}
REP(idx, k + 1, n) {
new_jun.push_back(jun[idx]);
}
} else if (best_type == 2) {
rep(idx, i + 1) {
new_jun.push_back(jun[idx]);
}
REP(idx, j + 1, k + 1) {
new_jun.push_back(jun[idx]);
}
for (int idx = j; idx >= i + 1; idx--) {
new_jun.push_back(jun[idx]);
}
REP(idx, k + 1, n) {
new_jun.push_back(jun[idx]);
}
} else if (best_type == 3) {
rep(idx, i + 1) {
new_jun.push_back(jun[idx]);
}
for (int idx = k; idx >= j + 1; idx--) {
new_jun.push_back(jun[idx]);
}
REP(idx, i + 1, j + 1) {
new_jun.push_back(jun[idx]);
}
REP(idx, k + 1, n) {
new_jun.push_back(jun[idx]);
}
}
swap(jun, new_jun);
}
}
}
}
static vector<int> dist(n);
rep(i, n) {
int s = jun[i], t = jun[(i + 1) % n];
dist[i] = hyou[s][t];
}
return calc_score(dist);
}
int double_bridge(vector<int> &jun) {
static vi erase_idx;
while (true) {
erase_idx.clear();
rep(i, 4) {
erase_idx.push_back(rnd(n));
}
sort(all(erase_idx));
UNIQUE(erase_idx);
if (erase_idx.size() == 4) {
break;
}
}
static vi new_jun;
new_jun.clear();
rep(i, erase_idx[0] + 1) {
new_jun.emplace_back(i);
}
REP(i, erase_idx[2] + 1, erase_idx[3] + 1) {
new_jun.emplace_back(i);
}
REP(i, erase_idx[1] + 1, erase_idx[2] + 1) {
new_jun.emplace_back(i);
}
REP(i, erase_idx[0] + 1, erase_idx[1] + 1) {
new_jun.emplace_back(i);
}
REP(i, erase_idx[3] + 1, n) {
new_jun.emplace_back(i);
}
swap(jun, new_jun);
return two_opt(jun);
}
vector<pii> calc_ans(const vi &jun) {
vector<pii> ans;
ans.emplace_back(1, 0);
rep(i, n) {
int s = jun[i], t = jun[(i + 1) % n];
pii keiyu = inter[s][t];
if (keiyu.first != -1) {
ans.emplace_back(2, keiyu.first);
}
if (keiyu.second != -1) {
ans.emplace_back(2, keiyu.second);
}
ans.emplace_back(1, t);
}
return ans;
}
void fine_tune(const vi &jun) {
vector<pii> ans = calc_ans(jun);
rep(i, m) {
using P = pair<pii, pii>;
static vector<P> tar;
tar.clear();
rep(j, ans.size() - 1) {
if (ans[j] == pii(2, i) or ans[j + 1] == pii(2, i)) {
tar.emplace_back(ans[j], ans[j + 1]);
}
}
int best_dist = inf;
pii best_dxy(0, 0);
for (int dy = -100; dy <= 100; dy++) {
for (int dx = -100; dx <= 100; dx++) {
if (not in(cd[i].first + dy, 0, 1001) or not in(cd[i].second + dx, 0, 1001)) {
continue;
}
pii ori = cd[i];
cd[i] = ori + pii(dy, dx);
int dist = 0;
for (auto [t1, t2] : tar) {
pii yx1, yx2;
if (t1.first == 1) {
yx1 = ab[t1.second];
} else {
yx1 = cd[t1.second];
}
if (t2.first == 1) {
yx2 = ab[t2.second];
} else {
yx2 = cd[t2.second];
}
int add = calc_dist(yx1, yx2);
if (t1.first == 1) {
add *= alpha;
}
if (t2.first == 1) {
add *= alpha;
}
dist += add;
}
if (chmin(best_dist, dist)) {
best_dxy = pii(dy, dx);
}
cd[i] = ori;
}
}
cd[i] = cd[i] + best_dxy;
}
}
int calc_score2(const vector<int> &jun) {
int sum = 0;
rep(i, jun.size()) {
auto [d, _] = find_min_inter(jun[i], jun[(i + 1) % jun.size()]);
sum += d;
}
return round(1e9 / (1000 + sqrt(sum)));
}
int move_inter(const vector<int> &jun, int score) {
double start_temp = 1000, end_temp = 0.1;
rep(try_num, 128) {
double rate = try_num / 127.0;
static vector<pii> ori_cd;
ori_cd = cd;
if (rnd(2)) {
rep(idx, m) {
cd[idx].first += rnd(-20, 20);
cd[idx].second += rnd(-20, 20);
cd[idx].first = min(max(cd[idx].first, 0), 1000);
cd[idx].second = min(max(cd[idx].second, 0), 1000);
}
} else {
int idx = try_num % m;
cd[idx].first += rnd(-30, 30);
cd[idx].second += rnd(-30, 30);
cd[idx].first = min(max(cd[idx].first, 0), 1000);
cd[idx].second = min(max(cd[idx].second, 0), 1000);
}
int new_score = calc_score2(jun);
double temp = start_temp + (end_temp - start_temp) * rate;
double prob = exp((new_score - score) / temp);
// if (new_score >= score) {
if (prob > (rnd(inf) / (double)inf)) {
score = new_score;
} else {
swap(cd, ori_cd);
}
}
return score;
}
void output(const vector<int> &jun) {
rep(i, m) {
cout << cd[i].first << " " << cd[i].second << endl;
}
vector<pii> ans = calc_ans(jun);
cout << ans.size() << endl;
for (auto [t, u] : ans) {
cout << t << " " << u + 1 << endl;
}
}
signed main() {
clock_t start_c = clock();
input();
vector<int> jun(n);
rep(i, n) {
jun[i] = i;
}
int score = two_opt(jun);
int best_score = score;
vi best_jun = jun;
vector<pii> best_cd = cd;
rep(try_num, inf) {
double sec = (double)(clock() - start_c) / CLOCKS_PER_SEC;
if (sec > 0.9) {
DEBUG(sec);
DEBUG(try_num);
break;
}
if (try_num % 4 == 0) {
int new_score = double_bridge(jun);
DEBUG(pii(score, new_score));
score = new_score;
continue;
}
static vector<pii> ori_cd;
ori_cd = cd;
// if (rnd(2)) {
// rep(idx, m) {
// cd[idx].first += rnd(-20, 20);
// cd[idx].second += rnd(-20, 20);
// cd[idx].first = min(max(cd[idx].first, 0), 1000);
// cd[idx].second = min(max(cd[idx].second, 0), 1000);
// }
// } else {
// int idx = rnd(m);
// cd[idx].first += rnd(-30, 30);
// cd[idx].second += rnd(-30, 30);
// cd[idx].first = min(max(cd[idx].first, 0), 1000);
// cd[idx].second = min(max(cd[idx].second, 0), 1000);
// }
int temp_score = move_inter(jun, score);
static vi ori_jun;
ori_jun = jun;
int new_score = two_opt(jun);
// DEBUG(score);
// DEBUG(temp_score);
// DEBUG(new_score);
if (new_score < score) {
cd = ori_cd;
swap(jun, ori_jun);
rep(i, n) {
rep(j, n) {
hyou[i][j] = ori_hyou[i][j];
inter[i][j] = ori_inter[i][j];
}
}
} else {
score = new_score;
if (score > best_score) {
best_score = score;
best_jun = jun;
best_cd = cd;
}
}
}
cd = best_cd;
jun = best_jun;
DEBUG(score);
DEBUG(best_score);
while (true) {
int ori_score = two_opt(jun);
fine_tune(jun);
int new_score = two_opt(jun);
DEBUG("two")
DEBUG(pii(ori_score, new_score));
if (ori_score == new_score) {
new_score = three_opt(jun);
DEBUG("three");
DEBUG(pii(ori_score, new_score));
if (ori_score == new_score) {
break;
}
}
}
output(jun);
}