結果

問題 No.2102 [Cherry Alpha *] Conditional Reflection
ユーザー Navier_BoltzmannNavier_Boltzmann
提出日時 2023-11-29 15:33:49
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,348 bytes
コンパイル時間 273 ms
コンパイル使用メモリ 82,060 KB
実行使用メモリ 344,552 KB
最終ジャッジ日時 2024-09-26 13:26:41
合計ジャッジ時間 79,279 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 49 ms
58,268 KB
testcase_01 AC 45 ms
55,936 KB
testcase_02 AC 1,168 ms
189,920 KB
testcase_03 AC 1,290 ms
249,652 KB
testcase_04 AC 1,166 ms
184,000 KB
testcase_05 AC 1,000 ms
120,692 KB
testcase_06 AC 1,303 ms
193,392 KB
testcase_07 AC 1,126 ms
262,780 KB
testcase_08 AC 577 ms
83,128 KB
testcase_09 AC 1,210 ms
265,944 KB
testcase_10 AC 739 ms
108,304 KB
testcase_11 AC 582 ms
135,992 KB
testcase_12 AC 1,000 ms
179,304 KB
testcase_13 AC 1,423 ms
265,064 KB
testcase_14 AC 1,057 ms
153,732 KB
testcase_15 AC 1,454 ms
207,660 KB
testcase_16 AC 1,762 ms
260,008 KB
testcase_17 WA -
testcase_18 AC 1,273 ms
255,536 KB
testcase_19 AC 837 ms
139,184 KB
testcase_20 AC 1,542 ms
265,140 KB
testcase_21 AC 877 ms
89,820 KB
testcase_22 AC 1,874 ms
266,596 KB
testcase_23 AC 1,891 ms
266,260 KB
testcase_24 AC 1,839 ms
266,580 KB
testcase_25 AC 1,855 ms
260,032 KB
testcase_26 AC 1,848 ms
266,144 KB
testcase_27 AC 1,872 ms
259,308 KB
testcase_28 AC 1,856 ms
259,192 KB
testcase_29 AC 1,859 ms
259,428 KB
testcase_30 AC 1,881 ms
259,440 KB
testcase_31 AC 2,400 ms
266,128 KB
testcase_32 AC 1,912 ms
259,724 KB
testcase_33 AC 1,831 ms
259,696 KB
testcase_34 AC 1,805 ms
266,540 KB
testcase_35 AC 1,863 ms
266,576 KB
testcase_36 AC 1,828 ms
266,652 KB
testcase_37 AC 1,840 ms
259,656 KB
testcase_38 AC 1,859 ms
266,368 KB
testcase_39 AC 1,885 ms
266,468 KB
testcase_40 AC 1,838 ms
267,028 KB
testcase_41 AC 1,878 ms
266,388 KB
testcase_42 AC 1,284 ms
151,604 KB
testcase_43 AC 1,290 ms
151,256 KB
testcase_44 AC 1,312 ms
151,524 KB
testcase_45 AC 1,331 ms
151,976 KB
testcase_46 AC 1,271 ms
152,168 KB
testcase_47 AC 1,332 ms
250,972 KB
testcase_48 AC 1,312 ms
251,016 KB
testcase_49 AC 1,315 ms
250,860 KB
testcase_50 AC 1,305 ms
251,096 KB
testcase_51 AC 1,315 ms
250,716 KB
testcase_52 AC 976 ms
343,624 KB
testcase_53 AC 999 ms
344,552 KB
testcase_54 AC 980 ms
344,396 KB
testcase_55 AC 1,050 ms
248,052 KB
testcase_56 AC 1,035 ms
248,572 KB
testcase_57 AC 1,044 ms
248,044 KB
testcase_58 AC 548 ms
200,720 KB
testcase_59 AC 1,868 ms
265,564 KB
testcase_60 AC 631 ms
81,048 KB
testcase_61 AC 1,046 ms
247,916 KB
testcase_62 AC 162 ms
79,536 KB
testcase_63 AC 687 ms
80,804 KB
testcase_64 AC 699 ms
80,552 KB
testcase_65 AC 716 ms
80,912 KB
testcase_66 AC 1,044 ms
248,136 KB
testcase_67 AC 1,235 ms
83,316 KB
testcase_68 AC 499 ms
79,512 KB
testcase_69 AC 1,253 ms
83,444 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

from collections import *
from itertools import *
from functools import *
from heapq import *
import sys,math
input = sys.stdin.readline

N = int(input())
class Rolling_hash():
    def __init__(self,S,mod_list = [1000000009,998244353,3000012541],base_num_list=[500009,500029,500041]):
        
        self.n = len(mod_list)
        self.S = S
        self.N = len(self.S)
        self.H = [[0]*(self.N+1) for _ in range(self.n)]
        self.b_inv = [[1]*self.N for _ in range(self.n)]
        self.b = [[1]*self.N for _ in range(self.n)]
        self.mod_list = mod_list
        
        for j in range(self.n):
            
            tb = base_num_list[j]
            base_num = base_num_list[j]
            mod = mod_list[j]
            tb_inv = 1
            base_inv = pow(base_num,mod-2,mod)
            tH = self.S[0]
            self.H[j][1] = tH
            
            for i in range(self.N-1):
                tH = (tH + self.S[i+1]*tb)%mod
                self.H[j][i+2] = tH
                self.b[j][i+1] = tb
                
                tb = (tb*base_num)%mod
                
                tb_inv *= base_inv
                tb_inv %= mod
                self.b_inv[j][i+1] = tb_inv
                # self.b[j][i+1] = tb
                
    def query(self,j,l,r):
        if l==r:
            return 0
        tmp = (self.H[j][r]-self.H[j][l])*self.b_inv[j][l]%self.mod_list[j]
        
        return tmp
        
        
X = [set(),set()]
for _ in range(N):
    s = list(input())[:-1]
    s = [ord(i)-ord('a')+1 for i in s] + [0]
    rh = Rolling_hash(s)
    n = len(s) - 1
    v0,v1 = rh.query(0,0,n),rh.query(1,0,n)
    if (v0 in X[0])&(v1 in X[1]):
        print('Yes')
    else:
        print('No')
    X[0].add(v0)
    X[1].add(v1)
    # print(_,v0,v1)
    for i in range(n-1):
        
        flg = 0
        
        v0 = (rh.query(flg,0,i)
            + rh.query(flg,i,i+1)*rh.b[flg][i+1]
            + rh.query(flg,i+1,i+2)*rh.b[flg][i]
            + rh.query(flg,i+2,n)*rh.b[flg][i+2])%rh.mod_list[flg]
        X[0].add(v0)
        flg = 1
        v1 = (rh.query(flg,0,i)
            + rh.query(flg,i,i+1)*rh.b[flg][i+1]
            + rh.query(flg,i+1,i+2)*rh.b[flg][i]
            + rh.query(flg,i+2,n)*rh.b[flg][i+2])%rh.mod_list[flg]
        X[1].add(v1)
        # print(i,v0,v1)
    # print(s)
0