#783463 (C++17) No.5007 Steiner Space Travel

提出ソース
結果

問題	No.5007 Steiner Space Travel
ユーザー	mai
提出日時	2022-07-30 20:47:49
言語	C++17 (gcc 12.3.0 + boost 1.83.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
	純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
テストケース

テストケース表示
入力	結果	実行時間実行使用メモリ
testcase_00	AC	903 ms 4,460 KB
testcase_01	AC	902 ms 4,488 KB
testcase_02	AC	902 ms 4,476 KB
testcase_03	AC	901 ms 4,368 KB
testcase_04	AC	901 ms 4,440 KB
testcase_05	AC	902 ms 4,372 KB
testcase_06	AC	902 ms 4,376 KB
testcase_07	AC	902 ms 4,360 KB
testcase_08	AC	902 ms 4,512 KB
testcase_09	AC	902 ms 4,372 KB
testcase_10	AC	902 ms 4,372 KB
testcase_11	AC	902 ms 4,372 KB
testcase_12	AC	902 ms 4,372 KB
testcase_13	AC	902 ms 4,368 KB
testcase_14	AC	902 ms 4,464 KB
testcase_15	AC	902 ms 4,460 KB
testcase_16	AC	901 ms 4,360 KB
testcase_17	AC	902 ms 4,456 KB
testcase_18	AC	902 ms 4,476 KB
testcase_19	AC	902 ms 4,360 KB
testcase_20	AC	902 ms 4,372 KB
testcase_21	AC	902 ms 4,372 KB
testcase_22	AC	902 ms 4,436 KB
testcase_23	AC	902 ms 4,372 KB
testcase_24	AC	902 ms 4,372 KB
testcase_25	AC	902 ms 4,368 KB
testcase_26	AC	902 ms 4,472 KB
testcase_27	AC	902 ms 4,364 KB
testcase_28	AC	901 ms 4,464 KB
testcase_29	AC	903 ms 4,368 KB
権限があれば一括ダウンロードができます
ソースコード

raw source code
#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;
}
yukicoder

結果

テストケース

ソースコード
