結果

問題 No.1695 Mirror Mirror
ユーザー LayCurseLayCurse
提出日時 2021-10-01 23:00:39
言語 C++17
(gcc 13.2.0 + boost 1.83.0)
結果
AC  
実行時間 108 ms / 2,000 ms
コード長 14,407 bytes
コンパイル時間 2,897 ms
コンパイル使用メモリ 225,260 KB
実行使用メモリ 15,028 KB
最終ジャッジ日時 2023-08-28 16:07:57
合計ジャッジ時間 7,647 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,480 KB
testcase_01 AC 2 ms
5,388 KB
testcase_02 AC 2 ms
5,412 KB
testcase_03 AC 2 ms
5,416 KB
testcase_04 AC 3 ms
5,656 KB
testcase_05 AC 2 ms
5,404 KB
testcase_06 AC 2 ms
5,404 KB
testcase_07 AC 2 ms
5,440 KB
testcase_08 AC 2 ms
5,448 KB
testcase_09 AC 2 ms
5,412 KB
testcase_10 AC 2 ms
5,404 KB
testcase_11 AC 2 ms
5,424 KB
testcase_12 AC 2 ms
5,436 KB
testcase_13 AC 2 ms
5,600 KB
testcase_14 AC 2 ms
5,420 KB
testcase_15 AC 2 ms
5,412 KB
testcase_16 AC 2 ms
5,556 KB
testcase_17 AC 2 ms
5,636 KB
testcase_18 AC 2 ms
5,420 KB
testcase_19 AC 2 ms
5,428 KB
testcase_20 AC 2 ms
5,380 KB
testcase_21 AC 99 ms
14,728 KB
testcase_22 AC 108 ms
14,880 KB
testcase_23 AC 97 ms
14,200 KB
testcase_24 AC 107 ms
14,352 KB
testcase_25 AC 5 ms
5,940 KB
testcase_26 AC 2 ms
5,396 KB
testcase_27 AC 2 ms
5,496 KB
testcase_28 AC 4 ms
5,860 KB
testcase_29 AC 2 ms
5,392 KB
testcase_30 AC 59 ms
11,344 KB
testcase_31 AC 85 ms
13,944 KB
testcase_32 AC 21 ms
7,496 KB
testcase_33 AC 95 ms
14,512 KB
testcase_34 AC 41 ms
9,360 KB
testcase_35 AC 82 ms
13,164 KB
testcase_36 AC 98 ms
14,548 KB
testcase_37 AC 36 ms
8,768 KB
testcase_38 AC 85 ms
12,884 KB
testcase_39 AC 30 ms
8,244 KB
testcase_40 AC 93 ms
13,700 KB
testcase_41 AC 102 ms
14,644 KB
testcase_42 AC 91 ms
14,488 KB
testcase_43 AC 56 ms
11,300 KB
testcase_44 AC 68 ms
12,444 KB
testcase_45 AC 54 ms
10,816 KB
testcase_46 AC 72 ms
12,164 KB
testcase_47 AC 68 ms
11,920 KB
testcase_48 AC 94 ms
14,204 KB
testcase_49 AC 101 ms
15,028 KB
testcase_50 AC 5 ms
6,060 KB
testcase_51 AC 5 ms
6,284 KB
testcase_52 AC 4 ms
5,836 KB
testcase_53 AC 4 ms
5,932 KB
testcase_54 AC 4 ms
5,880 KB
testcase_55 AC 53 ms
10,876 KB
testcase_56 AC 67 ms
12,196 KB
testcase_57 AC 59 ms
11,108 KB
testcase_58 AC 78 ms
13,520 KB
testcase_59 AC 67 ms
12,356 KB
testcase_60 AC 56 ms
11,060 KB
testcase_61 AC 34 ms
8,704 KB
testcase_62 AC 83 ms
14,088 KB
testcase_63 AC 89 ms
14,220 KB
testcase_64 AC 3 ms
5,396 KB
権限があれば一括ダウンロードができます

ソースコード

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;
}
;
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]);
// }
0