結果
| 問題 |
No.5007 Steiner Space Travel
|
| コンテスト | |
| ユーザー |
 mai
|
| 提出日時 | 2022-07-30 20:47:49 |
| 言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 903 ms / 1,000 ms |
| コード長 | 17,872 bytes |
| コンパイル時間 | 3,471 ms |
| 実行使用メモリ | 4,512 KB |
| スコア | 8,048,161 |
| 最終ジャッジ日時 | 2022-07-30 20:48:22 |
| 合計ジャッジ時間 | 33,092 ms |
|
ジャッジサーバーID （参考情報） |
judge12 / judge11 |
| 純コード判定しない問題か言語 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 30 |
ソースコード
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
// clang-format off
using namespace std;
using ll = long long int;
#define all(v) (v).begin(),(v).end()
#define repeat(cnt,l) for(typename remove_const<typename remove_reference<decltype(l)>::type>::type cnt={};(cnt)<(l);++(cnt))
#define rrepeat(cnt,l) for(auto cnt=(l)-1;0<=(cnt);--(cnt))
#define iterate(cnt,b,e) for(auto cnt=(b);(cnt)!=(e);++(cnt))
#define upto(cnt,b,e,step) for(auto cnt=(b);(cnt)<=(e);(cnt)+=(step))
#define downto(cnt,b,e,step) for(auto cnt=(b);(e)<=(cnt);(cnt)-=(step))
const long long MD = 998244353; const long double PI = 3.1415926535897932384626433832795L;
template<typename T1, typename T2> inline ostream& operator <<(ostream &o, const pair<T1, T2> p) { o << '(' << p.first << ':' << p.second << ')'; return o; }
template<typename T> inline T& chmax(T& to, const T& val) { return to = max(to, val); }
template<typename T> inline T& chmin(T& to, const T& val) { return to = min(to, val); }
void bye(string s, int code = 0) { cout << s << endl; exit(code); }
mt19937_64 randdev(8901016);
template<typename T, typename Random = decltype(randdev), typename enable_if<is_integral<T>::value>::type* = nullptr>
inline T rand(T l, T h, Random& rand = randdev) { return uniform_int_distribution<T>(l, h)(rand); }
template<typename T, typename Random = decltype(randdev), typename enable_if<is_floating_point<T>::value>::type* = nullptr>
inline T rand(T l, T h, Random& rand = randdev) { return uniform_real_distribution<T>(l, h)(rand); }template<typename T>
static ostream& operator<<(ostream& o, const std::vector<T>& v) {
o << "[ "; for(const auto& e : v) o<<e<<' ';
return o << ']';
}
template <typename I>
struct MyRangeFormat{ I b,e; MyRangeFormat(I _b, I _e):b(_b),e(_e){} };
template<typename I>
static ostream& operator<<(ostream& o, const MyRangeFormat<I>& f) {
o << "[ "; iterate(i,f.b,f.e) o<<*i<<' ';
return o << ']';
}
template <typename I>
struct MyMatrixFormat{
const I& p; long long n, m;
MyMatrixFormat(const I& _p, long long _n, long long _m):p(_p),n(_n),m(_m){}
};
template<typename I>
static ostream& operator<<(ostream& o, const MyMatrixFormat<I>& f) {
o<<'\n';
repeat(i,(f.n)) {
repeat(j,f.m) o<<f.p[i][j]<<' ';
o<<'\n';
}
return o;
}
struct LOG_t { ~LOG_t() { clog << endl; } };
#define LOG (LOG_t(),clog<<'L'<<__LINE__<<": ")
#define FMTA(m,w) (MyRangeFormat<decltype(m+0)>(m,m+w))
#define FMTR(b,e) (MyRangeFormat<decltype(e)>(b,e))
#define FMTV(v) FMTR(v.begin(),v.end())
#define FMTM(m,h,w) (MyMatrixFormat<decltype(m+0)>(m,h,w))
#if defined(_WIN32) || defined(_WIN64)
#define getc_x _getc_nolock
#define putc_x _putc_nolock
#elif defined(__GNUC__)
#define getc_x getc_unlocked
#define putc_x putc_unlocked
#else
#define getc_x getc
#define putc_x putc
#endif
class MaiScanner {
FILE* fp_;
constexpr bool isvisiblechar(char c) noexcept { return (0x21<=(c)&&(c)<=0x7E); }
public:
inline MaiScanner(FILE* fp):fp_(fp){}
template<typename T> void input_integer(T& var) noexcept {
var = 0; T sign = 1;
int cc = getc_x(fp_);
for (; cc < '0' || '9' < cc; cc = getc_x(fp_))
if (cc == '-') sign = -1;
for (; '0' <= cc && cc <= '9'; cc = getc_x(fp_))
var = (var << 3) + (var << 1) + cc - '0';
var = var * sign;
}
inline int c() noexcept { return getc_x(fp_); }
template<typename T, typename enable_if<is_integral<T>::value, nullptr_t>::type = nullptr>
inline MaiScanner& operator>>(T& var) noexcept { input_integer<T>(var); return *this; }
inline MaiScanner& operator>>(string& var) {
int cc = getc_x(fp_);
for (; !isvisiblechar(cc); cc = getc_x(fp_));
for (; isvisiblechar(cc); cc = getc_x(fp_))
var.push_back(cc);
return *this;
}
template<typename IT> inline void in(IT begin, IT end) { for (auto it = begin; it != end; ++it) *this >> *it; }
};
class MaiPrinter {
FILE* fp_;
public:
inline MaiPrinter(FILE* fp):fp_(fp){}
template<typename T>
void output_integer(T var) noexcept {
if (var == 0) { putc_x('0', fp_); return; }
if (var < 0)
putc_x('-', fp_),
var = -var;
char stack[32]; int stack_p = 0;
while (var)
stack[stack_p++] = '0' + (var % 10),
var /= 10;
while (stack_p)
putc_x(stack[--stack_p], fp_);
}
inline MaiPrinter& operator<<(char c) noexcept { putc_x(c, fp_); return *this; }
template<typename T, typename enable_if<is_integral<T>::value, nullptr_t>::type = nullptr>
inline MaiPrinter& operator<<(T var) noexcept { output_integer<T>(var); return *this; }
inline MaiPrinter& operator<<(const char* str_p) noexcept { while (*str_p) putc_x(*(str_p++), fp_); return *this; }
inline MaiPrinter& operator<<(const string& str) {
const char* p = str.c_str();
const char* l = p + str.size();
while (p < l) putc_x(*p++, fp_);
return *this;
}
template<typename IT> void join(IT begin, IT end, char sep = ' ') { for (bool b = 0; begin != end; ++begin, b = 1) b ? *this << sep << *begin : *this << *begin; }
};
MaiScanner scanner(stdin);
MaiPrinter printer(stdout);
// clang-format on
struct P {
using T = int;
T y, x;
inline explicit P(T _y, T _x) : y(_y), x(_x) {}
inline P() : y(0), x(0) {}
inline bool operator==(P p) const { return y == p.y && x == p.x; }
inline bool operator<(P p) const { return y == p.y ? x < p.x : y < p.y; }
inline P operator+(P p) const { return P(y + p.y, x + p.x); }
inline P operator-(P p) const { return P(y - p.y, x - p.x); }
inline P &operator+=(P p) {
y += p.y;
x += p.x;
return *this;
}
inline P &operator-=(P p) {
y -= p.y;
x -= p.x;
return *this;
}
inline P &operator*=(T m) {
y *= m;
x *= m;
return *this;
}
inline T distM(P p) const { return abs(y - p.y) + abs(x - p.x); }
inline T distC(P p) const { return max(abs(y - p.y), abs(x - p.x)); }
template <typename ITR> ITR nearestM(ITR begin, ITR end) const {
if (begin == end)
return end;
T best = distM(*begin);
ITR besti = begin;
for (ITR it = begin; ++it, it != end;) {
T m = distM(*it);
if (best < m) {
best = m;
besti = it;
}
}
return besti;
}
};
inline ostream &operator<<(ostream &os, P p) {
os << '(' << p.y << ',' << p.x << ')';
return os;
}
const P FourMoving[] = {P(-1, 0), P(0, 1), P(1, 0), P(0, -1)};
const P FiveMoving[] = {P(-1, 0), P(0, 1), P(1, 0), P(0, -1), P(0, 0)};
const P EightMoving[] = {P(-1, 0), P(0, 1), P(1, 0), P(0, -1),
P(-1, -1), P(-1, 1), P(1, -1), P(1, 1)};
template <typename C = std::chrono::milliseconds> class Timer {
std::chrono::system_clock::time_point tp_;
public:
static inline auto now() { return std::chrono::system_clock::now(); }
inline void tic() { tp_ = now(); }
inline auto toc() const {
return std::chrono::duration_cast<C>(now() - tp_).count();
}
inline Timer() : tp_(now()) {}
};
inline std::ostream &operator<<(std::ostream &o, const Timer<> &t) {
return o << (long long)t.toc();
}
template <typename T>
// using T = int;
struct F {
int height, width;
vector<T> data;
explicit F(int h, int w) : height(h), width(w), data(h * w) {}
F() : F(1, 1) {}
inline T &operator()(int y, int x) { return data[x + y * width]; }
inline T &operator()(P p) { return data[p.x + p.y * width]; }
inline T operator()(int y, int x) const { return data[x + y * width]; }
inline T operator()(P p) const { return data[p.x + p.y * width]; }
inline bool safe(int y, int x) const {
return 0 <= y && y < height && 0 <= x && x < width;
}
inline bool safe(P p) const {
return 0 <= p.y && p.y < height && 0 <= p.x && p.x < width;
}
inline void fill(T e) { std::fill(data.begin(), data.end(), e); }
inline void resize(int h, int w) {
height = h;
width = w;
data.resize(h * w);
}
void print(ostream &os, int setw_arg = 4) {
for (int y = 0; y < height; ++y) {
for (int x = 0; x < width; ++x)
os << setw(setw_arg) << operator()(y, x) << ' ';
os << '\n';
}
}
};
#include <limits>
//
const ll kAlpha = 5;
const int N = 100;
const int M = 8;
Timer<> g_timer;
//
struct Problem {
vector<P> planets;
F<ll> dist;
};
//
struct Solution {
vector<P> satellites;
F<ll> sat_dist;
Solution() : satellites(M), sat_dist(N + M, M) {}
void update(const Problem &problem) {
repeat(i, N) {
P p = problem.planets[i];
repeat(j, M) {
ll d = (p.x - satellites[j].x) * (p.x - satellites[j].x) +
(p.y - satellites[j].y) * (p.y - satellites[j].y);
d *= kAlpha;
sat_dist(i, j) = d;
}
}
repeat(i, M) {
P p = satellites[i];
repeat(j, M) {
ll d = (p.x - satellites[j].x) * (p.x - satellites[j].x) +
(p.y - satellites[j].y) * (p.y - satellites[j].y);
d *= 1;
sat_dist(N + i, j) = d;
}
}
}
};
//
struct Shortcut {
ll dist;
vector<int> path;
Shortcut(ll &&_dist, vector<int> &&_path)
: dist(_dist), path(std::move(_path)) {}
};
//
ll getDistance(const Problem &problem, const Solution &solution, int p, int q) {
if (p > q)
swap(p, q);
if (p < N && q < N) {
return problem.dist(p, q);
} else {
return solution.sat_dist(p, q - N);
}
}
//
ll swap2opt(const F<ll> &dist, int p, int q, int pb, int qa) {
LOG << pb << "-" << q << " " << dist(pb, q);
LOG << p << "-" << qa << " " << dist(p, qa);
LOG << pb << "-" << p << " " << -dist(pb, p);
LOG << q << "-" << qa << " " << -dist(q, qa);
return dist(pb, q) + dist(p, qa) - dist(pb, p) - dist(q, qa);
}
vector<int> optimize(const F<ll> &dist) {
// ステーションを経由して移動したい
// 普通の2opt
vector<int> sequence(N);
iota(all(sequence), 0);
ll current_distance = dist(sequence[0], sequence[N - 1]);
repeat(i, N - 1) { current_distance += dist(sequence[i], sequence[i + 1]); }
// set<ll> aaasss;
// repeat(i, N - 1) {
// aaasss.insert(dist(sequence[i], sequence[i + 1]));
// LOG << sequence[i] << "-" << sequence[i + 1] << " "
// << dist(sequence[i], sequence[i + 1]);
// }
clog << current_distance << endl;
while (g_timer.toc() < 900) {
// repeat(_, 100) {
// do not change startp
int a = rand(1, N - 2);
int b = rand(2, N - 1);
if (a == b)
b += 1;
int p = sequence[a];
int q = sequence[b];
if (p > q) {
swap(p, q);
swap(a, b);
}
int pb = sequence[a == 0 ? N - 1 : a - 1];
int qa = sequence[b == N - 1 ? 0 : b + 1];
#if 0
ll dd = swap2opt(dist, p, q, pb, qa);
if (dd < 0) {
// swap(sequence[a], sequence[b]);
if (a < b) {
reverse(sequence.begin() + a, sequence.begin() + b + 1);
} else {
reverse(sequence.begin() + b, sequence.begin() + a + 1);
}
current_distance += dd;
LOG << sequence;
// clog << "swap " << p << " and " << q << " score=" << current_distance
// << endl;
// ll aaaddd = dist(sequence[0], sequence[N - 1]);
// repeat(i, N - 1) { aaaddd += dist(sequence[i], sequence[i + 1]); }
// repeat(i, N - 1) {
// if (!aaasss.count(dist(sequence[i], sequence[i + 1])))
// LOG << "ADD!" << dist(sequence[i], sequence[i + 1]);
// LOG << sequence[i] << "-" << sequence[i + 1] << " "
// << dist(sequence[i], sequence[i + 1]);
// aaasss.erase(dist(sequence[i], sequence[i + 1]));
// }
// for (auto e : aaasss)
// LOG << "ERASE! " << e;
// if (aaaddd != current_distance) {
// LOG << "pb=" << pb << " qa=" << qa;
// clog << "[FAIL] swap " << p << " and " << q
// << " score=" << current_distance << " true=" << aaaddd << endl;
// abort();
// }
// aaasss.clear();
// repeat(i, N - 1) {
// aaasss.insert(dist(sequence[i], sequence[i + 1]));
// LOG << sequence[i] << "-" << sequence[i + 1] << " "
// << dist(sequence[i], sequence[i + 1]);
// }
}
#else
{
if (a < b) {
reverse(sequence.begin() + a, sequence.begin() + b + 1);
} else {
reverse(sequence.begin() + b, sequence.begin() + a + 1);
}
ll new_distance = dist(sequence[0], sequence[N - 1]);
repeat(i, N - 1) { new_distance += dist(sequence[i], sequence[i + 1]); }
if (current_distance > new_distance) {
current_distance = new_distance;
} else {
if (a < b) {
reverse(sequence.begin() + a, sequence.begin() + b + 1);
} else {
reverse(sequence.begin() + b, sequence.begin() + a + 1);
}
}
}
#endif
}
clog << current_distance << endl;
clog << 1e9 / (1000 + sqrt(current_distance)) << endl;
return sequence;
}
vector<vector<Shortcut>> calcRoute(const Problem &problem,
const Solution &solution) {
// ステーションを設置すると、惑星間の距離は短縮される。
// 惑星間を移動するために、どのような経路で移動すれば良いかを知りたい
vector<vector<Shortcut>> shortcut_table;
shortcut_table.reserve(N);
repeat(vi, N) {
vector<ll> visited(M, numeric_limits<ll>::max() / 4);
vector<int> previous(M, -1);
vector<Shortcut> shortcuts;
shortcuts.reserve(N);
repeat(i, N) {
// initialize as no-shourtcut distance
shortcuts.emplace_back(problem.dist(vi, i), vector<int>());
}
priority_queue<pair<ll, int>> que;
repeat(i, M) {
// vi -> satellite
ll d = getDistance(problem, solution, vi, N + i);
que.emplace(-d, i);
visited[i] = d;
}
while (!que.empty()) {
int xi = que.top().second;
ll d = -que.top().first;
que.pop();
if (visited[xi] < d)
continue;
// Update satellite -> satelite
repeat(i, M) {
if (i == xi)
continue;
ll dw = solution.sat_dist(N + xi, i);
if (d + dw < visited[i]) {
visited[i] = d + dw;
que.emplace(-(d + dw), i);
previous[i] = xi;
}
}
}
// // Update vi -> satellites -> i
repeat(ui, N) {
if (vi == ui)
continue;
pair<ll, int> best;
best.first = problem.dist(ui, vi);
best.second = -1;
repeat(xi, M) {
//
chmin(best, make_pair(visited[xi] + solution.sat_dist(ui, xi), xi));
}
if (best.second >= 0) {
vector<int> path = {N + best.second};
{
int p = best.second;
while (previous[p] != -1) {
p = previous[p];
path.push_back(N + p);
}
}
reverse(all(path));
shortcuts[ui].dist = best.first;
shortcuts[ui].path = std::move(path);
} else {
shortcuts[ui].dist = best.first;
shortcuts[ui].path.clear();
}
}
shortcut_table.push_back(std::move(shortcuts));
}
// Fix
repeat(i, N) {
repeat(j, N) {
if (shortcut_table[i][j].dist > shortcut_table[j][i].dist) {
abort();
}
}
}
return shortcut_table;
}
F<ll> shortcutToDistTable(const vector<vector<Shortcut>> &shortcut_table) {
F<ll> dist(N, N);
repeat(i, N) {
repeat(j, N) { dist(i, j) = shortcut_table[i][j].dist; }
}
repeat(i, N) {
repeat(j, N) { assert(dist(i, j) == dist(j, i)); }
}
return dist;
}
//
pair<Solution, vector<int>> solve(const Problem &problem) {
Solution solution;
solution.satellites[0] = P{250, 250};
solution.satellites[1] = P{500, 250};
solution.satellites[2] = P{750, 250};
solution.satellites[3] = P{250, 500};
solution.satellites[4] = P{750, 500};
solution.satellites[5] = P{250, 750};
solution.satellites[6] = P{500, 750};
solution.satellites[7] = P{750, 750};
solution.update(problem);
auto shortcut_table = calcRoute(problem, solution);
auto dist = shortcutToDistTable(shortcut_table);
auto sequence = optimize(dist);
// vector<int> sequence(N);
// iota(all(sequence), 0);
ll dddd = 0;
sequence.push_back(0);
vector<int> sequence_with_satellites;
repeat(i, sequence.size() - 1) {
int p = sequence[i];
int q = sequence[i + 1];
assert(p != q);
sequence_with_satellites.push_back(p);
sequence_with_satellites.insert(sequence_with_satellites.end(),
all(shortcut_table[p][q].path));
dddd += shortcut_table[p][q].dist;
}
sequence_with_satellites.push_back(0);
// repeat(i, sequence_with_satellites.size() - 1) {
// dddd += getDistance(problem, solution, sequence_with_satellites[i],
// sequence_with_satellites[i + 1]);
// }
clog << 1e9 / (1000 + sqrt(dddd)) << endl;
return make_pair(std::move(solution), std::move(sequence_with_satellites));
}
//
void outputResult(const pair<Solution, vector<int>> &solution) {
repeat(i, M) {
P p = solution.first.satellites[i];
printer << p.x << ' ' << p.y << '\n';
}
printer << solution.second.size() << '\n';
for (auto p : solution.second) {
if (p < N) {
printer << "1 " << p + 1 << '\n';
} else {
printer << "2 " << p - N + 1 << '\n';
}
}
}
//
Problem loadStdin() {
int n, m;
scanner >> n >> m;
assert(n == N);
assert(m == M);
vector<P> planets;
planets.reserve(N);
repeat(i, N) {
int x, y;
scanner >> x >> y;
planets.emplace_back(y, x);
}
F<ll> dist(N, N);
repeat(i, N) {
P p = planets[i];
upto(j, i + 1, N - 1, 1) {
ll d = (p.x - planets[j].x) * (p.x - planets[j].x) +
(p.y - planets[j].y) * (p.y - planets[j].y);
d *= kAlpha * kAlpha;
dist(i, j) = d;
dist(j, i) = d;
}
}
return Problem{std::move(planets), std::move(dist)};
}
//
int main() {
//
auto problem = loadStdin();
auto solution = solve(problem);
outputResult(solution);
return 0;
}