結果
| 問題 | No.1859 ><<< |
| ユーザー |
👑  Kazun
|
| 提出日時 | 2022-03-07 22:24:35 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
AC
|
| 実行時間 | 373 ms / 2,000 ms |
| コード長 | 5,093 bytes |
| コンパイル時間 | 1,784 ms |
| コンパイル使用メモリ | 86,648 KB |
| 実行使用メモリ | 155,072 KB |
| 最終ジャッジ日時 | 2023-09-30 01:24:23 |
| 合計ジャッジ時間 | 21,062 ms |
|
ジャッジサーバーID （参考情報） |
judge12 / judge11 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 102 ms
71,896 KB |
| testcase_01 | AC | 100 ms
72,028 KB |
| testcase_02 | AC | 103 ms
71,588 KB |
| testcase_03 | AC | 104 ms
72,040 KB |
| testcase_04 | AC | 373 ms
154,460 KB |
| testcase_05 | AC | 354 ms
154,780 KB |
| testcase_06 | AC | 342 ms
154,364 KB |
| testcase_07 | AC | 348 ms
155,072 KB |
| testcase_08 | AC | 353 ms
154,856 KB |
| testcase_09 | AC | 352 ms
154,976 KB |
| testcase_10 | AC | 164 ms
89,444 KB |
| testcase_11 | AC | 257 ms
120,348 KB |
| testcase_12 | AC | 230 ms
115,044 KB |
| testcase_13 | AC | 186 ms
101,612 KB |
| testcase_14 | AC | 220 ms
124,660 KB |
| testcase_15 | AC | 262 ms
140,292 KB |
| testcase_16 | AC | 313 ms
147,120 KB |
| testcase_17 | AC | 233 ms
131,456 KB |
| testcase_18 | AC | 310 ms
146,120 KB |
| testcase_19 | AC | 241 ms
126,440 KB |
| testcase_20 | AC | 280 ms
140,024 KB |
| testcase_21 | AC | 299 ms
149,296 KB |
| testcase_22 | AC | 249 ms
147,248 KB |
| testcase_23 | AC | 284 ms
140,020 KB |
| testcase_24 | AC | 267 ms
148,168 KB |
| testcase_25 | AC | 322 ms
147,264 KB |
| testcase_26 | AC | 263 ms
140,428 KB |
| testcase_27 | AC | 333 ms
147,020 KB |
| testcase_28 | AC | 281 ms
145,948 KB |
| testcase_29 | AC | 310 ms
145,452 KB |
| testcase_30 | AC | 297 ms
140,044 KB |
| testcase_31 | AC | 278 ms
139,764 KB |
| testcase_32 | AC | 325 ms
148,816 KB |
| testcase_33 | AC | 291 ms
140,188 KB |
| testcase_34 | AC | 264 ms
146,456 KB |
| testcase_35 | AC | 319 ms
149,252 KB |
| testcase_36 | AC | 309 ms
149,332 KB |
| testcase_37 | AC | 310 ms
140,468 KB |
| testcase_38 | AC | 345 ms
149,936 KB |
| testcase_39 | AC | 311 ms
149,372 KB |
| testcase_40 | AC | 282 ms
147,808 KB |
| testcase_41 | AC | 254 ms
149,380 KB |
| testcase_42 | AC | 305 ms
139,452 KB |
| testcase_43 | AC | 312 ms
146,852 KB |
| testcase_44 | AC | 318 ms
147,104 KB |
ソースコード
class Rolling_Hash():
def __init__(self,S,base,mod):
self.mod=mod
self.base=base
self.string=S
self.power=power=[1]*(len(S)+1)
L=len(S)
self.hash=h=[0]*(L+1)
v=0
for i in range(L):
#h[i+1]=v=(v*base+ord(S[i]))%mod
h[i+1]=v=(v*base+S[i])%mod
v=1
for i in range(L):
power[i+1]=v=(v*base)%mod
def __hasher(self, X):
assert len(X)<=len(self)
h=0
for i in range(len(X)):
h=(h*self.base+X[i])%self.mod
return h
def get(self,l,r):
return (self.hash[r]-self.hash[l]*self.power[r-l])%self.mod
def count(self,T,start=0):
alpha=self.__hasher(T)
K=0
for i in range(start,len(self)-len(T)+1):
if alpha==self[i:i+len(T)]:
K+=1
return K
def find(self,T,start=0):
alpha=self.__hasher(T)
for i in range(start,len(self)-len(T)+1):
if alpha==self[i:i+len(T)]:
return i
return -1
def rfind(self,T,start=0):
alpha=self.__hasher(T)
for i in range(len(self)-len(T),start-1,-1):
if alpha==self[i:i+len(T)]:
return i
return -1
def index(self,T,start=0):
alpha=self.__hasher(T)
for i in range(start,len(self)-len(T)+1):
if alpha==self[i:i+len(T)]:
return i
raise ValueError("substring not found")
def __getitem__(self,index):
if index.__class__==int:
if index<0:
index+=len(self.string)
assert 0<=index<len(self.string)
return self.get(index,index+1)
elif index.__class__==slice:
assert (index.step==None) or (index.step==1)
L=index.start if index.start else 0
R=index.stop if index.stop else len(self)
if L<0:L+=len(self)
if R<0:R+=len(self)
return self.get(L,R)
def __len__(self):
return len(self.string)
#=================================================
class Multi_Rolling_Hash():
def __init__(self, S, base, *mod):
self.string=S
self.__N=len(mod)
self.__base=base
self.__mod=mod
self.rh=[Rolling_Hash(S,base,m) for m in mod]
def get(self, l, r):
return tuple(H[l:r] for H in self.rh)
def __hasher(self, X):
assert len(X)<=len(self)
h=[0]*self.__N
for i in range(self.__N):
m=self.__mod[i]
a=0
for x in X:
a=(a*self.__base+x)%m
h[i]=a
return tuple(h)
def __getitem__(self, index):
if index.__class__==int:
if index<0:
index+=len(self.string)
assert 0<=index<len(self.string)
return tuple(H[index] for H in self.rh)
elif index.__class__==slice:
assert (index.step==None) or (index.step==1)
L=index.start if index.start else 0
R=index.stop if index.stop else len(self)
if L<0:L+=len(self)
if R<0:R+=len(self)
return tuple(H[L:R] for H in self.rh)
def count(self,T,start=0):
alpha=self.__hasher(T)
K=0
T_len=len(T)
for i in range(start,len(self)-len(T)+1):
if alpha==self[i:i+T_len]:
K+=1
return K
def find(self,T,start=0):
alpha=self.__hasher(T)
for i in range(start,len(self)-len(T)+1):
if alpha==self[i:i+len(T)]:
return i
return -1
def rfind(self,T,start=0):
alpha=self.__hasher(T)
for i in range(len(self)-len(T),start-1,-1):
if alpha==self[i:i+len(T)]:
return i
return -1
def index(self,T,start=0):
alpha=self.__hasher(T)
for i in range(start,len(self)-len(T)+1):
if alpha==self[i:i+len(T)]:
return i
raise ValueError("substring not found")
def __len__(self):
return len(self.string)
class Hasher():
def __init__(self, length, base, mod):
self.length=length
self.base=base
self.mod=mod
self.power=pw=[1]*length
for i in range(1,length):
pw[i]=(base*pw[i-1])%mod
def __repr__(self):
return "length: {}\nbase: {}\nmod: {}".format(self.length, self.base, self.mod)
def encode(self, S):
code=0; N=len(S)
for i in range(N):
#code+=ord(S[i])*self.power[N-1-i]%self.mod
code+=S[i]*self.power[N-1-i]%self.mod
return code%self.mod
def decode(self, S):
pass
#==================================================
from random import randint as ri
N=int(input())
A=list(map(int,input().split()))
S=input()
Mod1=10**9+7; Mod2=10**9+9
a=ri(2,Mod1-1); b=ri(2,Mod1-1); p=ri(2,Mod1-1)
B=[a if A[i%N]<A[(i+1)%N] else b for i in range(2*N-1)]
T=[a if S[i]=="<" else b for i in range(N-1)]
H=Multi_Rolling_Hash(B,p,Mod1,Mod2)
print(H.find(T))