結果
問題 | No.1695 Mirror Mirror |
ユーザー |
![]() |
提出日時 | 2021-10-01 22:39:16 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 16,015 bytes |
コンパイル時間 | 2,843 ms |
コンパイル使用メモリ | 228,640 KB |
最終ジャッジ日時 | 2025-01-24 19:18:17 |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 58 WA * 3 |
ソースコード
#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;};void*wmem;char memarr[96000000];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;}template<class T> int KMP(T A[], int As, T B[], int Bs, int res[] = NULL, int *fail = (int*)wmem){int i;int k;int cnt = 0;k = fail[0] = -1;for(i=(0);i<(Bs);i++){while(k>=0 && B[k]!=B[i]){k = fail[k];}fail[i+1] = ++k;}if(res != NULL){for(i=(0);i<(As);i++){res[i] = 0;}}k = 0;for(i=(0);i<(As);i++){while(k >= 0 && B[k] != A[i]){k = fail[k];}k++;if(k == Bs){cnt++;if(res != NULL){res[i-Bs+1] = 1;}k = fail[k];}}return cnt;}template<class T, class S> int KMP(T A[], int As, T B[], int Bs, S res[], int *fail = (int*)wmem){int i;int k;int cnt = 0;k = fail[0] = -1;for(i=(0);i<(Bs);i++){while(k>=0 && B[k]!=B[i]){k = fail[k];}fail[i+1] = ++k;}if(res != NULL){for(i=(0);i<(As);i++){res[i] = 0;}}k = 0;for(i=(0);i<(As);i++){while(k >= 0 && B[k] != A[i]){k = fail[k];}k++;if(k == Bs){cnt++;if(res != NULL){res[i-Bs+1] = 1;}k = fail[k];}}return cnt;}#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){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<(M);i++){tt[i] = T[m-1-i];}int KrdatlYV;int ao_dF3pO;int tU__gIr_;KrdatlYV = 0;ao_dF3pO = m;while(KrdatlYV < ao_dF3pO){if((KrdatlYV + ao_dF3pO)%2==0){tU__gIr_ = (KrdatlYV + ao_dF3pO) / 2;}else{tU__gIr_ = (KrdatlYV + ao_dF3pO + 1) / 2;}if(KMP(S,N,T,tU__gIr_)){KrdatlYV = tU__gIr_;}else{ao_dF3pO = tU__gIr_ - 1;}}k =ao_dF3pO;for(i=(0);i<(k);i++){dp[i+1] = 1;}int YREPHmFM;int jZyWAPpY;int jbtyPBGc;YREPHmFM = 0;jZyWAPpY = m;while(YREPHmFM < jZyWAPpY){if((YREPHmFM + jZyWAPpY)%2==0){jbtyPBGc = (YREPHmFM + jZyWAPpY) / 2;}else{jbtyPBGc = (YREPHmFM + jZyWAPpY + 1) / 2;}if(KMP(S,N,tt,jbtyPBGc)){YREPHmFM = jbtyPBGc;}else{jZyWAPpY = jbtyPBGc - 1;}}k =jZyWAPpY;for(i=(0);i<(k);i++){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 gEg5UqEA;int qSsg05KM;int Hjfu7Vx7;gEg5UqEA = 0;qSsg05KM =min_L(i, m-i);while(gEg5UqEA < qSsg05KM){if((gEg5UqEA + qSsg05KM)%2==0){Hjfu7Vx7 = (gEg5UqEA + qSsg05KM) / 2;}else{Hjfu7Vx7 = (gEg5UqEA + qSsg05KM + 1) / 2;}if( arr1.get_len(i,Hjfu7Vx7) == arr2.get_len(m-i,Hjfu7Vx7) ){gEg5UqEA = Hjfu7Vx7;}else{qSsg05KM = Hjfu7Vx7 - 1;}}k =qSsg05KM;chmax(e, i+1);while(e <= i+k){chmin(dp[e], dp[i] + 1);e++;}}return max_L(2, dp[m]);}int main(){wmem = memarr;{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(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,M) tt[i] = T[m-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(S,N,tt,k));// rep(i,k) dp[i+1] = 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]);// }