結果
| 問題 |
No.3121 Prime Dance
|
| ユーザー |
 hardenisthegoat
|
| 提出日時 | 2025-04-19 01:20:50 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
MLE
|
| 実行時間 | - |
| コード長 | 10,929 bytes |
| コンパイル時間 | 3,853 ms |
| コンパイル使用メモリ | 257,836 KB |
| 実行使用メモリ | 577,776 KB |
| 最終ジャッジ日時 | 2025-04-19 01:21:02 |
| 合計ジャッジ時間 | 10,619 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | -- * 2 |
| other | MLE * 1 -- * 20 |
ソースコード
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define ar array
#define int long long
#define ll long long
#define ld long double
#define pb push_back
#define eb emplace_back
#define pob pop_back()
#define nn "\n"
#define onn << "\n"
#define ee endl
#define oee << endl
#define ss " "
#define oss << " "
#define sei unordered_set<int, custom_hash>
#define ses unordered_set<string>
#define ma unordered_map
#define maii unordered_map<int, int, custom_hash>
#define vc vector
#define id1 int n; cin >> n;
#define gls getline(cin, s)
#define sinf 1e9
#define inf (int) 1e18
#define co cout <<
#define sp(i) setprecision(i) <<
#define f1(i, a) for (auto& i : a)
#define f2(i, j, a) for (auto& [i, j] : a)
#define f3(i, j, k, a) for (auto& [i, j, k] : a)
#define be(s) s.begin(), s.end()
#define rbe(s) s.rbegin(), s.rend()
#define bb(s) s.begin(), s.begin()
#define ctz(x) __builtin_ctzll(x)
#define cb(x) __builtin_popcountll(x)
#define ff(i, begin, end) for (__typeof(end) i = (begin) - ((begin) > (end)); i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end)))
#define i128 __int128_t
#define lb lower_bound
#define ub upper_bound
#define ook order_of_key
#define fbo find_by_order
#define fn function
#define bs bitset
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef unsigned long long ull;
typedef pair<int, string> pis;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<bool> vb;
typedef vector<string> vs;
typedef vector<double> vd;
typedef vector<pair<int,int>> vp;
typedef vector<vector<int>> vvi;
#pragma GCC optimize("Ofast,unroll-loops")
#ifdef LOCAL
#include "debug_util.h"
#else
#define help(...)
#define helpArray(...)
#define io
#define _time
#define _siu
#endif
template<class T> using pq = priority_queue<T>;
template<class T> using pqg = priority_queue<T, vector<T>, greater<T>>;
template< typename T1, typename T2 >
ostream &operator<<(ostream &os, const pair< T1, T2 >& p) { os << p.first << " " << p.second; return os;}
template< typename T1, typename T2 >
istream &operator>>(istream &is, pair< T1, T2 > &p) {is >> p.first >> p.second; return is;}
template< typename T >
ostream &operator<<(ostream &os, const vector< T > &v) { for(int i = 0; i < (int) v.size(); i++) {os << v[i] << (i + 1 != v.size() ? " " : "");} return os;}
template< typename T >
istream &operator>>(istream &is, vector< T > &v) { for(T &in : v) is >> in; return is;}
struct custom_hash {
static uint64_t splitmix64(uint64_t x) {
// http://xorshift.di.unimi.it/splitmix64.c
x += 0x9e3779b97f4a7c15;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
return x ^ (x >> 31);
}
size_t operator()(uint64_t x) const {
static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
return splitmix64(x + FIXED_RANDOM);
}
};
template<class T>
bool constexpr chmin(T &a, T b) {
if (a > b) {a = b;return true;}
return false;
}
template<class T>
bool constexpr chmax(T &a, T b) {
if (a < b) {a = b;return true;}
return false;
}
// stable sort
template <typename T>
vector<int> argsort(const vector<T> &A) {
vector<int> ans(sz(A));
iota(be(ans), 0);
sort(be(ans),
[&](int i, int j) { return (A[i] == A[j] ? i < j : A[i] < A[j]); });
return ans;
}
//64b
long long lsb(long long x) { return x & -x;}
long long msb(long long x) { return (1ll << (63-__builtin_clzll(x))) & x;}
void onb(long long& x, int i) { x |= (1ll << i);}
void offb(long long& x, int i) { x &= ~(1ll << i);}
bool hb(long long x, int i) { return ((1ll << i) & x) != 0;}
long long bit(long long x) { return 1ll << x;}
void YES(bool t = 1) { cout << (t ? "YES" : "NO") << "\n"; }
void NO(bool t = 1) { YES(!t); }
void Yes(bool t = 1) { cout << (t ? "Yes" : "No") << "\n"; }
void No(bool t = 1) { Yes(!t); }
template<typename T>
vector<pair<T, int>> pfy(vector<T>& f) {
vector<pair<T, int>> v;
for (int i = 0; i < f.size(); i++) {
v.push_back({f[i], i});
}
return v;
}
bool inrange(int i, int j, int limi, int limj) {
return i >= 0 && i < limi && j >= 0 && j < limj;
}
typedef tuple<int,int,int> iii;
vector<char> cao = {'C','D','H','S'};
int dr8[] = {0,-1,0, 1, 1, 1, -1, -1};
int dc8[] = {-1, 0, 1, 0, 1, -1, 1, -1};
//n,w,e,s
int dr[] = {-1, 1, 0, 0};
int dc[] = {0,0,-1, 1};
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int rand(int l, int r)
{
uniform_int_distribution<int> uid(l, r);
return uid(rng);
}
// Define a tree-based set with integer keys
template <typename T>
using Tee = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
vector<int> spf;
vector<int> primes;
void sieve(int N) {
spf.assign(N, 0);
for(int i = 2; i < N; i++) {
if (spf[i] == 0) spf[i] = i, primes.push_back(i);
int siz = primes.size();
for (int j = 0; j < siz && i * primes[j] < N && primes[j] <= spf[i]; j++) {
spf[i * primes[j]] = primes[j];
}
}
}
void sui() {
auto isprime = [&](int cur) {
if (cur <= 1) return false;
return spf[cur] == cur;
};
int h,w;
cin>>h>>w;
vi a(4);
cin>>a;
f1(i,a) --i;
vs v(h);
cin>>v;
set<vi> vis;
vi cur(h);
onb(cur[a[0]], a[1]);
vis.insert(cur);
map<vi, vi> ans;
vi cmax(4);
vi curr(4);
auto dfs = [&](auto&& dfs, int c, int d) -> void {
if (c == a[2] && d == a[3]) {
ans[cur] = cmax;
return;
}
vis.insert(cur);
ff(i,0,4) {
if (inrange(c+dr[i], d+dc[i],h,w)) {
if (!hb(cur[c+dr[i]], d+dc[i])) {
bool inced = 0;
curr[i]++;
if (curr[i] > cmax[i]) {
inced = 1;
cmax[i]++;
}
onb(cur[c+dr[i]], d+dc[i]);
if (!vis.count(cur)) dfs(dfs,c+dr[i], d+dc[i]);
offb(cur[c+dr[i]], d+dc[i]);
curr[i]--;
if (inced) cmax[i]--;
}
}
}
};
dfs(dfs,a[0],a[1]);
bool haiz = 0;
auto thisisfailing = [&](vector<int>& b) -> int {
int can = 0;
int tot = 0;
int p1 = abs(b[1]-b[0]);
ff(i,0,primes.size()-1) {
if (primes[i]+p1 < primes[i+1]) {
return -1;
}
if (primes[i] < min(b[0], b[1])) continue;
if (isprime(primes[i]+p1)) {
tot += 2*primes[i]+p1;
++can;
break;
}
}
int p2 = abs(b[3]-b[2]);
ff(i,0,primes.size()-1) {
if (primes[i]+p2 < primes[i+1]) {
return - 1;
}
if (primes[i] < min(b[0], b[1])) continue;
if (isprime(primes[i]+p2)) {
tot += 2*primes[i]+p2;
++can;
break;
}
}
if (can != 2) return -1;
return tot;
};
if (a[0] == a[2]) {
vi aa;
rep(i,0,min(a[1],a[3])) {
if (inrange(a[0]+1,i,h,w)) {
if (v[a[0]+1][i] == '.') aa = {1,1,min(a[1],a[3])-i,max(a[1],a[3])-i};
}
if (inrange(a[0]-1,i,h,w)) {
if (v[a[0]-1][i] == '.') aa = {1,1,min(a[1],a[3])-i,max(a[1],a[3])-i};
}
}
vi b;
ff(i,min(a[1],a[3]), max(a[1],a[3])+1) {
if (inrange(a[0]+1,i,h,w)) {
if (v[a[0]+1][i] == '.') b = {1,1,0,max(a[1],a[3])-min(a[1], a[3])};
}
if (inrange(a[0]-1,i,h,w)) {
if (v[a[0]-1][i] == '.') b = {1,1,0,max(a[1],a[3])-min(a[1], a[3])};
}
}
vi c;
ff(i,w, max(a[1],a[3])+1) {
if (inrange(a[0]+1,i,h,w)) {
if (v[a[0]+1][i] == '.') c = {1,1,i-max(a[1],a[3]),i-min(a[1], a[3])};
}
if (inrange(a[0]-1,i,h,w)) {
if (v[a[0]-1][i] == '.') c = {1,1,i-max(a[1],a[3]),i-min(a[1], a[3])};
}
}
int mn = inf;
if (!aa.empty()) {
int cur = thisisfailing(aa);
if (cur != -1) chmin(mn, cur);
}
if (!b.empty()) {
int cur = thisisfailing(b);
if (cur != -1) chmin(mn, cur);
}
if (!c.empty()) {
int cur = thisisfailing(c);
if (cur != -1) chmin(mn, cur);
}
if (mn == inf) {
co -1 onn;
return;
}
co mn onn;
return;
} else if (a[1]==a[3]) {
vi aa;
rep(i,0,min(a[0],a[2])) {
if (inrange(i,a[1]+1,h,w)) {
if (v[i][a[1]+1] == '.') aa = {min(a[0],a[2])-i,max(a[0],a[2])-i,1,1};
}
if (inrange(i,a[1]-1,h,w)) {
if (v[i][a[1]-1] == '.') aa = {min(a[0],a[2])-i,max(a[0],a[2])-i,1,1};
}
}
vi b;
ff(i,min(a[0],a[2]), max(a[0],a[2])+1) {
if (inrange(i,a[1]+1,h,w)) {
if (v[i][a[1]+1] == '.') b = {max(a[0],a[2])-min(a[0],a[2]),0,1,1};
}
if (inrange(i,a[1]-1,h,w)) {
if (v[i][a[1]-1] == '.') b = {max(a[0],a[2])-min(a[0],a[2]),0,1,1};
}
}
vi c;
ff(i,h, max(a[0],a[2])+1) {
if (inrange(i,a[1]+1,h,w)) {
if (v[i][a[1]+1] == '.') c = {i-max(a[0],a[2]),i-min(a[0],a[2]),1,1};
}
if (inrange(i,a[1]-1,h,w)) {
if (v[i][a[1]-1] == '.') c = {i-max(a[0],a[2]),i-min(a[0],a[2]),1,1};
}
}
int mn = inf;
if (!a.empty()) {
int cur = thisisfailing(aa);
if (cur != -1) chmin(mn, cur);
}
if (!b.empty()) {
int cur = thisisfailing(b);
if (cur != -1) chmin(mn, cur);
}
if (!c.empty()) {
int cur = thisisfailing(c);
if (cur != -1) chmin(mn, cur);
}
if (mn == inf) {
co -1 onn;
return;
}
co mn onn;
return;
} else {
haiz = 1;
}
if (!haiz) {
co -1 onn;
return;
}
// help(b);
if (ans.empty()) {
co -1 onn;
} else {
//udlr
// auto thisisfailing = [&](vector<int>& b) -> int {
// int can = 0;
// int tot = 0;
// int p1 = abs(b[1]-b[0]);
// ff(i,0,primes.size()-1) {
// if (primes[i]+p1 < primes[i+1]) {
// return -1;
// }
// if (primes[i] < min(b[0], b[1])) continue;
// if (isprime(primes[i]+p1)) {
// tot += 2*primes[i]+p1;
// ++can;
// break;
// }
// }
// int p2 = abs(b[3]-b[2]);
// ff(i,0,primes.size()-1) {
// if (primes[i]+p2 < primes[i+1]) {
// return - 1;
// }
// if (primes[i] < min(b[0], b[1])) continue;
// if (isprime(primes[i]+p2)) {
// tot += 2*primes[i]+p2;
// ++can;
// break;
// }
// }
// return tot;
// };
int mn = inf;
f2(a,b,ans) {
help(a,b);
int cur = thisisfailing(b);
if (cur != -1) chmin(mn, cur);
}
if (mn == inf) {
co -1 onn;
return;
}
co mn onn;
}
}
signed main() {
cin.tie(NULL);
ios_base::sync_with_stdio(false);
auto start = std::chrono::high_resolution_clock::now();
io;
int n = 1;
// cin >> n;
sieve(1e7+5);
ff(i,0,n)
sui();
_time;
return 0;
}