結果
問題 | No.2454 Former < Latter |
ユーザー |
![]() |
提出日時 | 2023-09-01 22:24:18 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 716 ms / 2,000 ms |
コード長 | 677 bytes |
コンパイル時間 | 360 ms |
コンパイル使用メモリ | 82,372 KB |
実行使用メモリ | 81,664 KB |
最終ジャッジ日時 | 2025-01-03 09:29:35 |
合計ジャッジ時間 | 13,739 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 23 |
ソースコード
Q=int(input()) mod=67280421310721 for _ in range(Q): N=int(input()) S=input() x100=[1]*(N+1) for i in range(1,N+1): x100[i]=x100[i-1]*100 x100[i]%=mod v=[0]*N w=0 for i in range(N): w*=100 w%=mod x=ord(S[i])-ord('a') w+=x+1 w%=mod v[i]=w result=0 for i in range(1,N): l=0 r=min(i,N-i) r2=r while True: m=(l+r+1)//2 a=v[m-1] b=v[i+m-1]-v[i-1]*(x100[m]) b%=mod if a==b: l=m else: r=m-1 if l==r: break if l==r2: if N>2*i: result+=1 else: p=ord(S[l]) q=ord(S[i+l]) if p<q: result+=1 print(result)