結果

問題 No.1695 Mirror Mirror
ユーザー LayCurseLayCurse
提出日時 2021-10-01 22:30:53
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 14,763 bytes
コンパイル時間 2,846 ms
コンパイル使用メモリ 225,860 KB
実行使用メモリ 19,652 KB
最終ジャッジ日時 2024-07-19 12:20:33
合計ジャッジ時間 8,566 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 3 ms
7,628 KB
testcase_01 AC 3 ms
7,624 KB
testcase_02 AC 4 ms
7,632 KB
testcase_03 AC 4 ms
7,756 KB
testcase_04 WA -
testcase_05 WA -
testcase_06 AC 3 ms
7,628 KB
testcase_07 AC 4 ms
7,620 KB
testcase_08 AC 4 ms
9,668 KB
testcase_09 AC 4 ms
7,628 KB
testcase_10 AC 4 ms
7,628 KB
testcase_11 AC 4 ms
9,676 KB
testcase_12 AC 4 ms
7,752 KB
testcase_13 AC 3 ms
7,632 KB
testcase_14 AC 4 ms
7,748 KB
testcase_15 AC 4 ms
7,624 KB
testcase_16 AC 3 ms
7,620 KB
testcase_17 AC 3 ms
7,752 KB
testcase_18 AC 3 ms
7,624 KB
testcase_19 AC 3 ms
7,756 KB
testcase_20 AC 3 ms
7,624 KB
testcase_21 AC 147 ms
17,224 KB
testcase_22 AC 155 ms
17,180 KB
testcase_23 AC 102 ms
16,696 KB
testcase_24 AC 112 ms
19,652 KB
testcase_25 AC 84 ms
13,388 KB
testcase_26 AC 3 ms
7,760 KB
testcase_27 AC 3 ms
7,752 KB
testcase_28 AC 5 ms
9,800 KB
testcase_29 WA -
testcase_30 AC 104 ms
13,836 KB
testcase_31 AC 184 ms
16,108 KB
testcase_32 AC 69 ms
13,340 KB
testcase_33 AC 146 ms
16,660 KB
testcase_34 AC 97 ms
12,868 KB
testcase_35 AC 130 ms
15,400 KB
testcase_36 AC 119 ms
16,712 KB
testcase_37 AC 117 ms
12,616 KB
testcase_38 AC 125 ms
15,232 KB
testcase_39 AC 70 ms
10,440 KB
testcase_40 AC 101 ms
16,076 KB
testcase_41 AC 121 ms
16,836 KB
testcase_42 AC 127 ms
16,840 KB
testcase_43 AC 115 ms
13,488 KB
testcase_44 AC 106 ms
14,928 KB
testcase_45 AC 70 ms
13,124 KB
testcase_46 AC 109 ms
14,280 KB
testcase_47 AC 117 ms
15,432 KB
testcase_48 AC 156 ms
16,632 KB
testcase_49 AC 144 ms
17,092 KB
testcase_50 AC 6 ms
9,804 KB
testcase_51 AC 7 ms
10,180 KB
testcase_52 AC 5 ms
8,136 KB
testcase_53 AC 5 ms
8,136 KB
testcase_54 AC 5 ms
8,140 KB
testcase_55 AC 72 ms
13,004 KB
testcase_56 AC 76 ms
14,408 KB
testcase_57 AC 73 ms
15,172 KB
testcase_58 AC 138 ms
16,968 KB
testcase_59 AC 126 ms
14,668 KB
testcase_60 AC 75 ms
13,276 KB
testcase_61 AC 51 ms
11,084 KB
testcase_62 AC 107 ms
19,492 KB
testcase_63 AC 109 ms
16,536 KB
testcase_64 AC 3 ms
7,880 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;
}
;
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 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);
  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);
//   res <?= solve();
//   reverse(S,S+N);
//   reverse(T,T+M);
//   res <?= solve();
//   wt(if[res==int_inf, -1, res]);
// }
0