結果
問題 | No.1695 Mirror Mirror |
ユーザー |
![]() |
提出日時 | 2021-10-01 23:00:39 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 168 ms / 2,000 ms |
コード長 | 14,407 bytes |
コンパイル時間 | 3,245 ms |
コンパイル使用メモリ | 226,660 KB |
最終ジャッジ日時 | 2025-01-24 19:24:39 |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 61 |
ソースコード
#pragma GCC optimize("Ofast")#pragma GCC optimize("unroll-loops")#pragma GCC optimize("inline")#include<bits/stdc++.h>using namespace std;template<class T> struct cLtraits_identity{using type = T;};template<class T> using cLtraits_try_make_signed =typename conditional<is_integral<T>::value,make_signed<T>,cLtraits_identity<T>>::type;template <class S, class T> struct cLtraits_common_type{using tS = typename cLtraits_try_make_signed<S>::type;using tT = typename cLtraits_try_make_signed<T>::type;using type = typename common_type<tS,tT>::type;};template<class S, class T> inline auto min_L(S a, T b)-> typename cLtraits_common_type<S,T>::type{return (typename cLtraits_common_type<S,T>::type) a <= (typename cLtraits_common_type<S,T>::type) b ? a : b;}template<class S, class T> inline auto max_L(S a, T b)-> typename cLtraits_common_type<S,T>::type{return (typename cLtraits_common_type<S,T>::type) a >= (typename cLtraits_common_type<S,T>::type) b ? a : b;}struct Rand{unsigned x;unsigned y;unsigned z;unsigned w;Rand(void){x=123456789;y=362436069;z=521288629;w=(unsigned)time(NULL);}Rand(unsigned seed){x=123456789;y=362436069;z=521288629;w=seed;}inline unsigned get(void){unsigned t;t = (x^(x<<11));x=y;y=z;z=w;w = (w^(w>>19))^(t^(t>>8));return w;}inline double getUni(void){return get()/4294967296.0;}inline int get(int a){return (int)(a*getUni());}inline int get(int a, int b){return a+(int)((b-a+1)*getUni());}inline long long get(long long a){return(long long)(a*getUni());}inline long long get(long long a, long long b){return a+(long long)((b-a+1)*getUni());}inline double get(double a, double b){return a+(b-a)*getUni();}inline int getExp(int a){return(int)(exp(getUni()*log(a+1.0))-1.0);}inline int getExp(int a, int b){return a+(int)(exp(getUni()*log((b-a+1)+1.0))-1.0);}};inline int my_getchar_unlocked(){static char buf[1048576];static int s = 1048576;static int e = 1048576;if(s == e && e == 1048576){e = fread_unlocked(buf, 1, 1048576, stdin);s = 0;}if(s == e){return EOF;}return buf[s++];}inline void rd(int &x){int k;int m=0;x=0;for(;;){k = my_getchar_unlocked();if(k=='-'){m=1;break;}if('0'<=k&&k<='9'){x=k-'0';break;}}for(;;){k = my_getchar_unlocked();if(k<'0'||k>'9'){break;}x=x*10+k-'0';}if(m){x=-x;}}inline void rd(char &c){int i;for(;;){i = my_getchar_unlocked();if(i!=' '&&i!='\n'&&i!='\r'&&i!='\t'&&i!=EOF){break;}}c = i;}inline int rd(char c[]){int i;int sz = 0;for(;;){i = my_getchar_unlocked();if(i!=' '&&i!='\n'&&i!='\r'&&i!='\t'&&i!=EOF){break;}}c[sz++] = i;for(;;){i = my_getchar_unlocked();if(i==' '||i=='\n'||i=='\r'||i=='\t'||i==EOF){break;}c[sz++] = i;}c[sz]='\0';return sz;}struct MY_WRITER{char buf[1048576];int s;int e;MY_WRITER(){s = 0;e = 1048576;}~MY_WRITER(){if(s){fwrite_unlocked(buf, 1, s, stdout);}}};MY_WRITER MY_WRITER_VAR;void my_putchar_unlocked(int a){if(MY_WRITER_VAR.s == MY_WRITER_VAR.e){fwrite_unlocked(MY_WRITER_VAR.buf, 1, MY_WRITER_VAR.s, stdout);MY_WRITER_VAR.s = 0;}MY_WRITER_VAR.buf[MY_WRITER_VAR.s++] = a;}inline void wt_L(char a){my_putchar_unlocked(a);}inline void wt_L(int x){int s=0;int m=0;char f[10];if(x<0){m=1;x=-x;}while(x){f[s++]=x%10;x/=10;}if(!s){f[s++]=0;}if(m){my_putchar_unlocked('-');}while(s--){my_putchar_unlocked(f[s]+'0');}}template<class T, class U> inline T GCD_L(T a, U b){T r;while(b){r=a;a=b;b=r%a;}return a;}template<class S, class T> inline int arrcmp(int As, S A[], int Bs, T B[]){int i;for(i=0;;i++){if(i==As && As==Bs){break;}if(i==As){return -1;}if(i==Bs){return 1;}if(A[i] < B[i]){return -1;}if(A[i] > B[i]){return 1;}}return 0;}template<class S, class T> inline S chmin(S &a, T b){if(a>b){a=b;}return a;}template<class S, class T> inline S chmax(S &a, T b){if(a<b){a=b;}return a;}#define ROLLING_HASH_MOD (2305843009213693951ULL)#define ROLLING_HASH_PRIMITIVE_ROOT (3)#define ROLLING_HASH_MAX_MEMORY (2000000)int ROLLING_HASH_MEM;unsigned long long ROLLING_HASH_BASE;unsigned long long ROLLING_HASH_IBASE;unsigned long long*ROLLING_HASH_PW = NULL;unsigned long long*ROLLING_HASH_IPW = NULL;inline unsigned long long rollingHash61_mul(unsigned long long a, unsigned long long b){__uint128_t r = (__uint128_t) a * b;a = (r >> 61) + (r & ROLLING_HASH_MOD);if(a >= ROLLING_HASH_MOD){a -= ROLLING_HASH_MOD;}return a;}inline unsigned long long rollingHash61_pow(unsigned long long a, unsigned long long b){unsigned long long r = 1;for(;;){if(b&1){r = rollingHash61_mul(r, a);}if(b==0){break;}b >>= 1;a = rollingHash61_mul(a, a);}return r;}void rollingHashInit(){int i;Rand rnd;unsigned long long x;for(i=(0);i<(20);i++){rnd.get(2);}do{x = rnd.get(1.0, (double)(ROLLING_HASH_MOD-2));}while(GCD_L(x, ROLLING_HASH_MOD-1)!= 1);ROLLING_HASH_BASE = rollingHash61_pow(ROLLING_HASH_PRIMITIVE_ROOT, x);ROLLING_HASH_IBASE = rollingHash61_pow(ROLLING_HASH_BASE, ROLLING_HASH_MOD - 2);}void rollingHash_expand(int k){int i;if(ROLLING_HASH_MEM >= k){return;}ROLLING_HASH_MEM =max_L(2 * ROLLING_HASH_MEM, k);assert(ROLLING_HASH_MEM <= 2 * ROLLING_HASH_MAX_MEMORY);ROLLING_HASH_PW = (unsigned long long*) realloc(ROLLING_HASH_PW, ROLLING_HASH_MEM * sizeof(unsigned long long));ROLLING_HASH_IPW = (unsigned long long*) realloc(ROLLING_HASH_IPW, ROLLING_HASH_MEM * sizeof(unsigned long long));ROLLING_HASH_PW[0] = 1;for(i=(1);i<(ROLLING_HASH_MEM);i++){ROLLING_HASH_PW[i] = rollingHash61_mul(ROLLING_HASH_PW[i-1], ROLLING_HASH_BASE);}ROLLING_HASH_IPW[0] = 1;for(i=(1);i<(ROLLING_HASH_MEM);i++){ROLLING_HASH_IPW[i] = rollingHash61_mul(ROLLING_HASH_IPW[i-1], ROLLING_HASH_IBASE);}}struct rollingHash{long long len;unsigned long long hs;template<class T> void set(int N, T A[]){int i;long long tmp;hs = 0;len = N;rollingHash_expand(N);for(i=(0);i<(N);i++){tmp = A[i] % ((long long)ROLLING_HASH_MOD);if(tmp < 0){tmp += ROLLING_HASH_MOD;}hs += rollingHash61_mul(tmp, ROLLING_HASH_PW[i]);if(hs >= ROLLING_HASH_MOD){hs -= ROLLING_HASH_MOD;}}}template<class S, class T> void change(long long ind, S bef, T aft){long long tmp1;long long tmp2;tmp1 = bef % ((long long)ROLLING_HASH_MOD);tmp2 = aft % ((long long)ROLLING_HASH_MOD);tmp1 = tmp2 - tmp1;if(tmp1 < 0){tmp1 += ROLLING_HASH_MOD;}if(tmp1 < 0){tmp1 += ROLLING_HASH_MOD;}if(tmp1 >= ROLLING_HASH_MOD){tmp1 -= ROLLING_HASH_MOD;}if(ind+1 <= ROLLING_HASH_MAX_MEMORY || ind+1 >= ROLLING_HASH_MEM){rollingHash_expand(ind+1);hs += rollingHash61_mul(tmp1, ROLLING_HASH_PW[ind]);}else{hs += rollingHash61_mul(tmp1, rollingHash61_pow(ROLLING_HASH_BASE, ind));}if(hs >= ROLLING_HASH_MOD){hs -= ROLLING_HASH_MOD;}}void push_front(rollingHash a){if(a.len + 1 <= ROLLING_HASH_MAX_MEMORY || a.len + 1 >= ROLLING_HASH_MEM){rollingHash_expand(a.len + 1);hs = rollingHash61_mul(hs, ROLLING_HASH_PW[a.len]);}else{hs = rollingHash61_mul(hs, rollingHash61_pow(ROLLING_HASH_BASE, a.len));}hs += a.hs;if(hs >= ROLLING_HASH_MOD){hs -= ROLLING_HASH_MOD;}len += a.len;}void push_back(rollingHash a){if(len + 1 <= ROLLING_HASH_MAX_MEMORY || len + 1 >= ROLLING_HASH_MEM){rollingHash_expand(len + 1);hs += rollingHash61_mul(a.hs, ROLLING_HASH_PW[len]);}else{hs += rollingHash61_mul(a.hs, rollingHash61_pow(ROLLING_HASH_BASE, len));}if(hs >= ROLLING_HASH_MOD){hs -= ROLLING_HASH_MOD;}len += a.len;}void pop_front(rollingHash a){if(hs >= a.hs){hs -= a.hs;}else{hs = hs + ROLLING_HASH_MOD - a.hs;}if(a.len + 1 <= ROLLING_HASH_MAX_MEMORY || a.len + 1 >= ROLLING_HASH_MEM){rollingHash_expand(a.len + 1);hs = rollingHash61_mul(hs, ROLLING_HASH_IPW[a.len]);}else{hs = rollingHash61_mul(hs, rollingHash61_pow(ROLLING_HASH_IBASE, a.len));}len -= a.len;}void pop_back(rollingHash a){unsigned long long tmp;if(len + 1 <= ROLLING_HASH_MAX_MEMORY || len + 1 >= ROLLING_HASH_MEM){rollingHash_expand(len + 1);tmp = rollingHash61_mul(a.hs, ROLLING_HASH_PW[len]);}else{tmp = rollingHash61_mul(a.hs, rollingHash61_pow(ROLLING_HASH_BASE, len));}if(hs >= tmp){hs -= tmp;}else{hs = hs + ROLLING_HASH_MOD - tmp;}len -= a.len;}bool operator==(const rollingHash a){return len == a.len && hs == a.hs;}bool operator!=(const rollingHash a){return len != a.len || hs != a.hs;}};template<class T> rollingHash calcRollingHash(int N, T A[]){rollingHash res;res.set(N, A);return res;}struct rollingHashSubarrays{unsigned long long*hs;int mem;int len;void set(){hs = NULL;mem = len = 0;}void free(){if(mem){delete[] hs;}}void expand(int k){if(mem >= k){return;}free();mem =max_L(2*mem, k);hs = new unsigned long long[mem];}template<class T> void set(int N, T A[]){int i;long long tmp;if(N <= 0){return;}rollingHash_expand(N);expand(N);len = N;tmp = A[0] % ((long long)ROLLING_HASH_MOD);if(tmp < 0){tmp += ROLLING_HASH_MOD;}hs[0] = tmp;for(i=(1);i<(N);i++){tmp = A[i] % ((long long)ROLLING_HASH_MOD);if(tmp < 0){tmp += ROLLING_HASH_MOD;}hs[i] = hs[i-1] + rollingHash61_mul(tmp, ROLLING_HASH_PW[i]);if(hs[i] >= ROLLING_HASH_MOD){hs[i] -= ROLLING_HASH_MOD;}}}rollingHash get_len(int s, int len){unsigned long long x;rollingHash res;res.len = len;rollingHash_expand(s+1);if(s == 0){res.hs = hs[len-1];}else{if(hs[s+len-1] >= hs[s-1]){res.hs = hs[s+len-1] - hs[s-1];}else{res.hs = hs[s+len-1] + ROLLING_HASH_MOD - hs[s-1];}res.hs = rollingHash61_mul(res.hs, ROLLING_HASH_IPW[s]);}return res;}rollingHash get(int a, int b){return get_len(a, b - a + 1);}rollingHashSubarrays(){set();}~rollingHashSubarrays(){free();}};int N;int M;char S[500000+2];char T[500000+2];char tt[500000+2];int dp[500000+2];rollingHashSubarrays arr1;rollingHashSubarrays arr2;int solve(){int i;int j;int k;int m;int e;if(M%2){return 1073709056;}m = M / 2;for(i=(0);i<(m);i++){if(T[i] != T[M-1-i]){return 1073709056;}}if(m <= N){int Q5VJL1cS;for(Q5VJL1cS=(0);Q5VJL1cS<(2);Q5VJL1cS++){reverse(S,S+N);for(i=(0);i<(m);i++){tt[i] = S[i];}for(i=(0);i<(m);i++){tt[m+i] = S[m-1-i];}if(arrcmp(M,T,M,tt)==0){return 1;}}}for(i=(0);i<(m+1);i++){dp[i] = 1073709056;}for(i=(0);i<(N);i++){tt[i] = S[N-1-i];}for(i=(0);i<(min_L(m, N));i++){if(S[i] != T[i]){break;}if(i==N-1){chmin(dp[i+1], 1);}else{chmin(dp[i+1], 1);}}for(i=(0);i<(m);i++){tt[i] = T[m-1-i];}arr1.set(m, T);arr2.set(m, tt);e = 1;for(i=(0);i<(m);i++){int ZIeRIny5;int iMWUTgY_;int AlM5nNnR;ZIeRIny5 = 0;iMWUTgY_ =min_L(i, m-i);while(ZIeRIny5 < iMWUTgY_){if((ZIeRIny5 + iMWUTgY_)%2==0){AlM5nNnR = (ZIeRIny5 + iMWUTgY_) / 2;}else{AlM5nNnR = (ZIeRIny5 + iMWUTgY_ + 1) / 2;}if( arr1.get_len(i,AlM5nNnR) == arr2.get_len(m-i,AlM5nNnR) ){ZIeRIny5 = AlM5nNnR;}else{iMWUTgY_ = AlM5nNnR - 1;}}k =iMWUTgY_;chmax(e, i+1);while(e <= i+k){chmin(dp[e], dp[i] + 1);e++;}}return max_L(2, dp[m]);}int main(){{rollingHashInit();}int res = 1073709056;rd(N);rd(M);rd(S);rd(T);chmin(res, solve());reverse(S,S+N);reverse(T,T+M);chmin(res, solve());if(res==1073709056){wt_L(-1);wt_L('\n');}else{wt_L(res);wt_L('\n');}return 0;}// cLay version 20210926-1// --- original code ---// int N, M;// char S[5d5+2], T[], tt[];// int dp[];//// rollingHashSubarrays arr1, arr2;//// int solve(){// int i, j, k, m, e;//// if(M%2) return int_inf;// m = M / 2;// rep(i,m) if(T[i] != T[M-1-i]) return int_inf;//// if(m <= N) rep(2){// reverse(S,S+N);// rep(i,m) tt[i] = S[i];// rep(i,m) tt[m+i] = S[m-1-i];// if(arrcmp(M,T,M,tt)==0) return 1;// }//// rep(i,m+1) dp[i] = int_inf;//// rep(i,N) tt[i] = S[N-1-i];//// // k = bsearch_max[int,k,0,m](KMP(S,N,T,k));// // rep(i,k) dp[i+1] <?= 1;// // k = bsearch_max[int,k,0,m](KMP(tt,N,T,k));// // rep(i,k) dp[i+1] <?= 2;// rep(i,min(m,N)){// if(S[i] != T[i]) break;// dp[i+1] <?= if[i==N-1, 1, 1];// }// // wt(dp(m+1));//// rep(i,m) tt[i] = T[m-1-i];// arr1.set(m, T);// arr2.set(m, tt);// e = 1;//// rep(i,m){// k = bsearch_max[int,k,0,min(i,m-i)]( arr1.get_len(i,k) == arr2.get_len(m-i,k) );// e >?= i+1;// while(e <= i+k) dp[e] <?= dp[i] + 1, e++;// }//// // wt(dp(m+1));// return max(2,dp[m]);// }//// {// int res = int_inf;// rd(N,M,S,T);// res <?= solve();// reverse(S,S+N);// reverse(T,T+M);// res <?= solve();// wt(if[res==int_inf, -1, res]);// }