結果

問題 No.3121 Prime Dance
コンテスト
ユーザー Yu_212
提出日時 2025-04-19 10:37:50
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
MLE  
実行時間 -
コード長 5,034 bytes
コンパイル時間 4,173 ms
コンパイル使用メモリ 292,880 KB
実行使用メモリ 688,676 KB
最終ジャッジ日時 2025-04-19 10:38:07
合計ジャッジ時間 15,552 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 2
other AC * 2 WA * 4 TLE * 2 MLE * 3 -- * 10
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

const int iinf = 1e9;
const ll inf = 1e18;
template<ll mod>
struct Mint {
    using M=Mint; ll v;
    M& put(ll x) { v=(x<mod)?x:x-mod; return *this; }
    Mint(ll x=0) { put(x%mod+mod); }
    M operator+(M m) {return M().put(v+m.v);}
    M operator-(M m) {return M().put(v+mod-m.v);}
    M operator*(M m) {return M().put(v*m.v%mod);}
    M operator/(M m) {return M().put(v*m.inv().v%mod);}
    M operator+=(M m) { return put(v+m.v); }
    M operator-=(M m) { return put(v+mod-m.v); }
    M operator*=(M m) { return put(v*m.v%mod); }
    M operator/=(M m) { return put(v*m.inv().v%mod); }
    bool operator==(M m) { return v==m.v; }
    M pow(ll m) const {
        M x=v, res=1;
        while (m) {
            if (m&1) res=res*x;
            x=x*x; m>>=1;
        }
        return res;
    }
    M inv() { return pow(mod-2); }
};
template<ll mod>
ostream&operator<<(ostream&o,Mint<mod>v){return o<<v.v;}


template<typename T>
ostream& operator<<(ostream &o, vector<T> v) {
    for (int i = 0; i < v.size(); i++)
        o << v[i] << (i+1<v.size()?" ":"");
    return o;
}
template <typename T>
struct SegTree {
    using F = function<T(T, T)>;
    int n;
    F f;
    T ti;
    vector<T> dat;
    SegTree() {}
    SegTree(F f, T ti,int num) : f(f), ti(ti) {
        n = max(__bit_ceil(num), 1);
        dat.assign(n << 1, ti);
    }
    SegTree(F f,T ti,vector<T>&v):SegTree(f,ti,v.size()){
        for (int i = 0; i < v.size(); i++)
            dat[n + i] = v[i];
        for(int i=n-1;i;i--) dat[i]=f(dat[i*2], dat[i*2+1]);
    }
    void set_val(int k, T x) {
        dat[k += n] = x;
        while(k >>= 1) dat[k] = f(dat[k*2], dat[k*2+1]);
    }
    T query(int a, int b) {
        if (a >= b) return ti;
        T vl = ti, vr = ti;
        for (int l=a+n, r=b+n; l<r; l>>=1, r>>=1) {
            if (l & 1) vl = f(vl, dat[l++]);
            if (r & 1) vr = f(dat[--r], vr);
        }
        return f(vl, vr);
    }
};
struct Edge { int to; ll cost; };

const int MOD = 998244353;

// a^e mod
ll modpow(ll a, ll e=MOD-2){
    ll r=1;
    while(e){
        if(e&1) r=r*a%MOD;
        a=a*a%MOD;
        e>>=1;
    }
    return r;
}

using mint = Mint<MOD>;
using i128 = __int128_t;
using ull = unsigned long long;
i128 pow128(i128 a,ull d,ull m){//remove m,i128->mint64
    i128 res=1;
    while (d) { if (d&1) (res*=a)%=m; (a*=a)%=m; d>>=1; }
    return res;
}
bool is_prime(ull n) {
    if (n <= 1 || (n > 2 && n % 2 == 0)) return false;
    //  mint64::set_mod(n);
    // {2,7,61,-1} -> n < 4759123141 (= 2^32)
    int test[] = {2,3,5,7,11,13,17,19,23,-1}; // n<1e16
    ull d = n - 1, s = 0;
    while (d % 2 == 0) ++s, d /= 2;
    for (int i = 0; test[i] < n && test[i] != -1; i++) {
        auto x = pow128(test[i], d, n);
        if (x == 1) goto end;
        for (int r = 0; r < s; r++) {
            if (x == n - 1) goto end;
            (x *= x) %= n;
        }
        return false;
        end:;
    }
    return true;
}


int main() {
    cin.tie(0)->sync_with_stdio(false);


    int H, W;
    cin >> H >> W;
    int sx, sy, gx, gy;
    cin >> sx >> sy >> gx >> gy;
    // 1-indexed -> 0-index
    sx--; sy--; gx--; gy--;
    vector<string> grid(H);
    for (int i = 0; i < H; i++) {
        cin >> grid[i];
    }

    int maxMoves = H * W;
    // visited を vector で管理: H x W x (maxMoves+1) x (maxMoves+1)
    vector visited(H, vector(W, vector(maxMoves+1, vector(maxMoves+1, false))));

    struct State { int x, y, v, h; };
    queue<pair<State,int>> q;

    visited[sx][sy][0][0] = true;
    q.push({{sx, sy, 0, 0}, 0});

    int dx[4] = {1, -1, 0, 0};
    int dy[4] = {0, 0, 1, -1};

    while (!q.empty()) {
        auto [st, dist] = q.front(); q.pop();
        for (int k = 0; k < 4; k++) {
            int nx = st.x + dx[k], ny = st.y + dy[k];
            if (nx<0||nx>=H||ny<0||ny>=W) continue;
            if (grid[nx][ny]=='#') continue;
            int nv = st.v + (k<2), nh = st.h + (k>=2);
            if (nv>maxMoves||nh>maxMoves) continue;
            if (!visited[nx][ny][nv][nh]) {
                visited[nx][ny][nv][nh] = true;
                q.push({{nx, ny, nv, nh}, dist + 1});
            }
        }
    }
    int dv = abs(sx - gx);
    int dh = abs(sy - gy);
    int ans = iinf;
    for (int i = 1; i <= maxMoves; i++) {
        for (int j = 1; j <= maxMoves; j++) {
            if (visited[gx][gy][i][j]) {
                int mv = (i-dv)/2;
                int mh = (j-dh)/2;
                if (dv % 2 == 1 && (mv != 2 || !is_prime(mv + dv))) continue;
                if (dh % 2 == 1 && (mh != 2 || !is_prime(mh + dh))) continue;
                if (dv % 2 == 0) while (!is_prime(mv) || !is_prime(mv+dv)) mv++;
                if (dh % 2 == 0) while (!is_prime(mh) || !is_prime(mh+dh)) mh++;
                cout << mv << " " << mh << endl;
                ans = min(ans, mv + mv+dv + mh + mh+dh);
                break;
            }
        }
    }
    cout << (ans==iinf?-1:ans) << endl;

    return 0;
}
0