結果

問題 No.1695 Mirror Mirror
ユーザー LayCurse
提出日時 2021-10-01 22:32:48
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 15,169 bytes
コンパイル時間 2,822 ms
コンパイル使用メモリ 226,764 KB
最終ジャッジ日時 2025-01-24 19:16:05
ジャッジサーバーID
(参考情報)
judge1 / judge1
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 4
other AC * 58 WA * 3
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#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;
}
}
for(i=(0);i<(m+1);i++){
dp[i] = 1073709056;
}
int cTE1_r3A;
int RZTsC2BF;
int FmcKpFmN;
cTE1_r3A = 0;
RZTsC2BF = m;
while(cTE1_r3A < RZTsC2BF){
if((cTE1_r3A + RZTsC2BF)%2==0){
FmcKpFmN = (cTE1_r3A + RZTsC2BF) / 2;
}
else{
FmcKpFmN = (cTE1_r3A + RZTsC2BF + 1) / 2;
}
if(KMP(S,N,T,FmcKpFmN)){
cTE1_r3A = FmcKpFmN;
}
else{
RZTsC2BF = FmcKpFmN - 1;
}
}
k =RZTsC2BF;
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 V9aVTaxx;
int APIVbQlN;
int YREPHmFM;
V9aVTaxx = 0;
APIVbQlN =min_L(i, m-i);
while(V9aVTaxx < APIVbQlN){
if((V9aVTaxx + APIVbQlN)%2==0){
YREPHmFM = (V9aVTaxx + APIVbQlN) / 2;
}
else{
YREPHmFM = (V9aVTaxx + APIVbQlN + 1) / 2;
}
if( arr1.get_len(i,YREPHmFM) == arr2.get_len(m-i,YREPHmFM) ){
V9aVTaxx = YREPHmFM;
}
else{
APIVbQlN = YREPHmFM - 1;
}
}
k =APIVbQlN;
chmax(e, i+1);
while(e <= i+k){
chmin(dp[e], dp[i] + 1);
e++;
}
}
return dp[m];
}
int main(){
wmem = memarr;
{
rollingHashInit();
}
int res = 1073709056;
rd(N);
rd(M);
rd(S);
rd(T);
if(arrcmp(N,S,M,T)==0){
res = 0;
}
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;
//
// rep(i,m+1) dp[i] = int_inf;
//
// k = bsearch_max[int,k,0,m](KMP(S,N,T,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 dp[m];
// }
//
// {
// int res = int_inf;
// rd(N,M,S,T);
// if(arrcmp(N,S,M,T)==0) res = 0;
// res <?= solve();
// reverse(S,S+N);
// reverse(T,T+M);
// res <?= solve();
// wt(if[res==int_inf, -1, res]);
// }
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0