結果
問題 | No.1695 Mirror Mirror |
ユーザー |
![]() |
提出日時 | 2024-12-17 05:01:44 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 249 ms / 2,000 ms |
コード長 | 1,237 bytes |
コンパイル時間 | 433 ms |
コンパイル使用メモリ | 82,568 KB |
実行使用メモリ | 166,460 KB |
最終ジャッジ日時 | 2024-12-17 05:01:55 |
合計ジャッジ時間 | 10,045 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 61 |
ソースコード
from collections import deque def Manacher(S): N=len(S) manacher=[None]*N i,j=0,0 while i<N: while 0<=i-j and i+j<N and S[i-j]==S[i+j]: j+=1 manacher[i]=j k=1 while 0<=i-k and k+manacher[i-k]<j: manacher[i+k]=manacher[i-k] k+=1 i+=k j-=k return manacher N,M=map(int,input().split()) S=input() T=input() if T==T[::-1] and M%2==0: TT=["."] for t in T: TT.append(t) TT.append(".") manacher=[(c-1)//2 for c in Manacher(TT)[::2]] palindrome=[i for i in range(M+1)] r=0 for i in range(M+1): while r<=i+manacher[i]: palindrome[r]=i r+=1 inf=1<<30 ans=inf if S==T: ans=0 for _ in range(2): le=0 for s,t in zip(S,T): if s==t: le+=1 else: break cnt=0 cur=M while True: if le*2>=cur: ans=min(ans,cnt+1) break if cur<=palindrome[cur//2]*2: break cur=palindrome[cur//2]*2 cnt+=1 S=S[::-1] if ans==inf: ans=-1 else: ans=-1 print(ans)