結果
問題 |
No.1695 Mirror Mirror
|
ユーザー |
![]() |
提出日時 | 2024-12-17 10:31:24 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 30 ms / 2,000 ms |
コード長 | 2,958 bytes |
コンパイル時間 | 3,828 ms |
コンパイル使用メモリ | 278,756 KB |
実行使用メモリ | 8,340 KB |
最終ジャッジ日時 | 2024-12-17 10:31:31 |
合計ジャッジ時間 | 7,155 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 61 |
ソースコード
//#undef LOCAL #include <bits/stdc++.h> using namespace std; using uint = unsigned int; using ll = long long; using ull = unsigned long long; template<class T> using V = vector<T>; template<class T> using VV = V<V<T>>; constexpr ll TEN(int n) { return (n == 0) ? 1 : 10 * TEN(n-1); } #define FOR(i, a, b) for(int i=(int)(a);i<(int)(b);i++) #define rep(i,N) for(int i=0;i<(int)(N);i++) #define rep1(i,N) for(int i=1;i<=(int)(N);i++) #define fs first #define sc second #define eb emplace_back #define pb eb #define all(x) x.begin(),x.end() template<class T, class U> void chmin(T& t, const U& u) { if (t > u) t = u; } template<class T, class U> void chmax(T& t, const U& u) { if (t < u) t = u; } #ifdef LOCAL #define show(x) cerr << __LINE__ << " : " << #x << " = " << (x) << endl #else #define show(x) true #endif template <class T, class U> ostream& operator<<(ostream& os, const pair<T, U>& p) { return os << "P(" << p.first << ", " << p.second << ")"; } template <class T> ostream& operator<<(ostream& os, const V<T>& v) { os << "["; for (auto d : v) os << d << ", "; return os << "]"; } // cin.tie(nullptr); // ios::sync_with_stdio(false); // cout << fixed << setprecision(20); //境界iを中心とする最長回文の長さ/2 template <class S> V<int> manacher(const S& s) { int n = int(s.size()); V<int> r(n); if (n == 0) return r; r[0] = 1; for (int i = 1, j = 0; i < n; i++) { int& k = r[i]; k = (j + r[j] <= i) ? 0 : min(j + r[j] - i, r[2 * j - i]); while (0 <= i - k && i + k < n && s[i - k] == s[i + k]) k++; if (j + r[j] < i + r[i]) j = i; } return r; } //文字iを中心とする最長回文の長さ template <class S> V<int> manacher_even(const S& s) { int n = int(s.size()); V<int> r(n + 1); for (int i = 1, j = 0; i < n; i++) { int& k = r[i]; k = (j + r[j] <= i) ? 0 : min(j + r[j] - i, r[2 * j - i]); while (0 <= i - 1 - k && i + k < n && s[i - 1 - k] == s[i + k]) k++; if (j + r[j] < i + r[i]) j = i; } return r; } int main() { int N,M;cin>>N>>M; string S,T;cin>>S>>T; bool bl=M%2==0; for(int m=0;m<M;m++){ if(T[m]!=T[M-1-m]){ bl=false; } } const int inf=1<<30; int ans=inf; if(bl){ vector<int> man=manacher_even(T),pal(M+1); for(int m=0;m<M+1;m++){ pal[m]=m; } int r=0; for(int m=0;m<M+1;m++){ while(r<=m+man[m]){ pal[r]=m; r+=1; } } if(S==T){ ans=0; } for(int _=0;_<2;_++){ int le=0; for(int i=0;i<min(S.size(),T.size());i++){ if(S[i]==T[i]){ le+=1; } else{ break; } } int cnt=0,cur=M; while(1){ if(le*2>=cur){ ans=min(ans,cnt+1); break; } if(cur<=pal[cur/2]*2){ break; } cur=pal[cur/2]*2; cnt+=1; } reverse(S.begin(),S.end()); } } if(ans==inf){ ans=-1; } cout<<ans<<"\n"; }