結果

問題 No.1859 ><<<
ユーザー rin204
提出日時 2022-02-27 14:56:04
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 338 ms / 2,000 ms
コード長 907 bytes
コンパイル時間 232 ms
コンパイル使用メモリ 82,432 KB
実行使用メモリ 155,228 KB
最終ジャッジ日時 2024-07-05 14:37:25
合計ジャッジ時間 13,781 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 41
権限があれば一括ダウンロードができます

ソースコード

diff # 

class RollingHash():
    def __init__(self, s, base, mod):
        self.mod = mod
        self.pw = pw = [1]*(len(s)+1)

        l = len(s)
        self.h = h = [0]*(l+1)

        v = 0
        for i in range(l):
            h[i+1] = v = (v * base + ord(s[i])) % mod
        v = 1
        for i in range(l):
            pw[i+1] = v = v * base % mod
    def get(self, l, r):
        return (self.h[r] - self.h[l] * self.pw[r-l]) % self.mod
        
base = 37; mod = 8913478971241

n = int(input())
A = list(map(int, input().split()))
S = input()
T = []
for i in range(n - 1):
    if A[i] > A[i + 1]:
        T.append(">")
    else:
        T.append("<")
if A[n - 1] > A[0]:
    T.append(">")
else:
    T.append("<")
    
T = T + T
rh = RollingHash(T, base, mod)
S = RollingHash(S, base, mod)
S = S.get(0, n - 1)
for i in range(n):
    if rh.get(i, i + n - 1) == S:
        print(i)
        exit()
print(-1)
0