結果

問題 No.3121 Prime Dance
ユーザー Kude
提出日時 2025-04-19 02:42:34
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 44 ms / 2,000 ms
コード長 3,709 bytes
コンパイル時間 4,019 ms
コンパイル使用メモリ 311,840 KB
実行使用メモリ 20,188 KB
最終ジャッジ日時 2025-04-19 02:42:40
合計ジャッジ時間 5,271 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
namespace {
#pragma GCC diagnostic ignored "-Wunused-function"
#include<atcoder/all>
#pragma GCC diagnostic warning "-Wunused-function"
using namespace std;
using namespace atcoder;
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define rrep(i,n) for(int i = (int)(n) - 1; i >= 0; i--)
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
template<class T> bool chmax(T& a, const T& b) { if (a < b) { a = b; return true; } else return false; }
template<class T> bool chmin(T& a, const T& b) { if (b < a) { a = b; return true; } else return false; }
using ll = long long;
using P = pair<int,int>;
using VI = vector<int>;
using VVI = vector<VI>;
using VL = vector<ll>;
using VVL = vector<VL>;


pair<vector<int>, vector<int>> primes_lpf(const int n) {
  vector<int> primes; primes.reserve(n / 10);
  vector<int> lpf(n + 1);
  for (int i = 2; i <= n; i += 2) lpf[i] = 2;
  for (int i = 3; i <= n; i += 6) lpf[i] = 3;
  if (2 <= n) primes.push_back(2);
  if (3 <= n) primes.push_back(3);
  // 5 * x <= n, x <= floor(n / 5)
  const int n5 = n / 5;
  int x = 5;
  char add_next = 2;
  for (; x <= n5; x += add_next, add_next ^= 0x2 ^ 4) {
    int px = lpf[x];
    if (px == 0) {
      lpf[x] = px = x;
      primes.push_back(x);
    }
    for (int i = 2;; ++i) {
      int q = primes[i];
      int y = q * x;
      if (y > n) break;
      lpf[y] = q;
      if (q == px) break;
    }
  }
  for (; x <= n; x += add_next, add_next ^= 0x2 ^ 4) {
    if (lpf[x] == 0) {
      lpf[x] = x;
      primes.push_back(x);
    }
  }
  return {move(primes), move(lpf)};
}

constexpr int PSIZE = 1000000;
auto [primes, lpf] = primes_lpf(PSIZE);

constexpr int INF = 1001001001;
char s[40][40];
int dist[40][40][1600];
bool done[40][40][1600];

} int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int h, w;
  cin >> h >> w;
  int xs, ys, xt, yt;
  cin >> xs >> ys >> xt >> yt;
  xs--, ys--, xt--, yt--;
  bool flip = ys == yt;
  if (flip) swap(xs, ys), swap(xt, yt);
  rep(i, h) rep(j, w) {
    char c;
    cin >> c;
    if (c == 'S' || c == 'G') c = '.';
    if (flip) s[j][i] = c;
    else s[i][j] = c;
  }
  if (flip) swap(h, w);
  rep(i, 40) rep(j, 40) rep(k, 1600) dist[i][j][k] = INF;
  deque<tuple<int, int, int>> q;
  dist[xs][ys][0] = 0;
  q.emplace_back(xs, ys, 0);
  while (q.size()) {
    auto [i, j, k] = q.front(); q.pop_front();
    if (done[i][j][k]) continue;
    done[i][j][k] = true;
    int d = dist[i][j][k];
    if (i + 1 < h && s[i+1][j] == '.' && k + 1 < 1600 && chmin(dist[i+1][j][k+1], d)) q.emplace_front(i+1, j, k+1);
    if (i && s[i-1][j] == '.' && k + 1 < 1600 && chmin(dist[i-1][j][k+1], d)) q.emplace_front(i-1, j, k+1);
    if (j + 1 < w && s[i][j+1] == '.' && chmin(dist[i][j+1][k], d+1)) q.emplace_back(i, j+1, k);
    if (j && s[i][j-1] == '.' && chmin(dist[i][j-1][k], d+1)) q.emplace_back(i, j-1, k);
  }
  auto is_prime = [](int x) {
    return x >= 2 && lpf[x] == x;
  };
  int ans = INF;
  rep(k, 1600) if (k) {
    int d = dist[xt][yt][k];
    if (d == INF) continue;
    int dx = abs(xt - xs), dy = abs(yt - ys);
    assert(dx % 2 == k % 2 && dy % 2 == d % 2);
    int xsmall = (k - dx) / 2, ysmall = (d - dy) / 2;
    int cost = 0;
    for (auto [x, d] : {pair(xsmall, dx), pair(ysmall, dy)}) {
      if (d % 2) {
        if (x > 2 || !is_prime(2 + d)) {
          cost = INF;
          break;
        }
        cost += 2 + 2 + d;
      } else {
        for (int p : primes | views::drop(lower_bound(all(primes), x) - primes.begin())) {
          if (is_prime(p + d)) {
            cost += p + p + d;
            break;
          }
        }
      }
    }
    chmin(ans, cost);
  }
  if (ans == INF) ans = -1;
  cout << ans << '\n';
}
0