結果

問題 No.2102 [Cherry Alpha *] Conditional Reflection
コンテスト
ユーザー kys
提出日時 2022-10-14 22:01:44
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,158 bytes
コンパイル時間 143 ms
コンパイル使用メモリ 82,512 KB
実行使用メモリ 238,676 KB
最終ジャッジ日時 2024-06-26 14:28:10
合計ジャッジ時間 48,910 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 5 WA * 47 TLE * 1 -- * 17
権限があれば一括ダウンロードができます

ソースコード

diff # 

def main():
    from sys import stdin, setrecursionlimit
    # setrecursionlimit(1000000)
    input = stdin.readline
    def iinput(): return int(input())
    def sinput(): return input().rstrip()
    def i0input(): return int(input()) - 1
    def linput(): return list(input().split())
    def liinput(): return list(map(int, input().split()))
    def miinput(): return map(int, input().split())
    def li0input(): return list(map(lambda x: int(x) - 1, input().split()))
    def mi0input(): return map(lambda x: int(x) - 1, input().split())
    INF = 1000000000000000000
    MOD = 1000000007

    # 1-dimension Rolling Hash
    class RollingHash():
        def __init__(self, s, base=37, mod=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 = 10**9 + 9
    pw = None
    def rolling_hash(s):
        l = len(s)
        h = [0]*(l + 1)
        v = 0
        for i in range(l):
            h[i+1] = v = (v * base + ord(s[i])) % mod
        return h
    # RH前に、必要な長さの最大値分のpow-tableを計算しておく
    def setup_pw(l):
        global pw
        pw = [1]*(l + 1)
        v = 1
        for i in range(l):
            pw[i+1] = v = v * base % mod
    def get(h, l, r):
        return (h[r] - h[l] * pw[r-l]) % mod

    res = set()
    N = iinput()
    for _ in [0] * N:
        S = sinput()
        L = len(S)
        rh = RollingHash(S)
        a = rh.get(0, L)
        if a in res:
            print('Yes')
        else:
            print('No')
        res.add(a)
        T = list(S)
        for i in range(L-1):
            T[i], T[i+1] = T[i+1], T[i]
            U = ''.join(T)
            a = RollingHash(U).get(0, L)
            res.add(a)
            T[i], T[i+1] = T[i+1], T[i]
        

main()
0