結果

問題 No.2102 [Cherry Alpha *] Conditional Reflection
ユーザー kyskys
提出日時 2022-10-14 22:01:44
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,158 bytes
コンパイル時間 435 ms
コンパイル使用メモリ 87,052 KB
実行使用メモリ 240,236 KB
最終ジャッジ日時 2023-09-08 21:36:36
合計ジャッジ時間 55,834 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 70 ms
71,320 KB
testcase_01 AC 71 ms
71,488 KB
testcase_02 WA -
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 AC 212 ms
80,620 KB
testcase_09 WA -
testcase_10 AC 299 ms
93,640 KB
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 AC 264 ms
84,200 KB
testcase_22 WA -
testcase_23 WA -
testcase_24 WA -
testcase_25 WA -
testcase_26 WA -
testcase_27 WA -
testcase_28 WA -
testcase_29 WA -
testcase_30 WA -
testcase_31 WA -
testcase_32 WA -
testcase_33 WA -
testcase_34 WA -
testcase_35 WA -
testcase_36 WA -
testcase_37 WA -
testcase_38 WA -
testcase_39 WA -
testcase_40 WA -
testcase_41 WA -
testcase_42 WA -
testcase_43 WA -
testcase_44 WA -
testcase_45 WA -
testcase_46 WA -
testcase_47 WA -
testcase_48 WA -
testcase_49 WA -
testcase_50 WA -
testcase_51 WA -
testcase_52 TLE -
testcase_53 -- -
testcase_54 -- -
testcase_55 -- -
testcase_56 -- -
testcase_57 -- -
testcase_58 -- -
testcase_59 -- -
testcase_60 -- -
testcase_61 -- -
testcase_62 -- -
testcase_63 -- -
testcase_64 -- -
testcase_65 -- -
testcase_66 -- -
testcase_67 -- -
testcase_68 -- -
testcase_69 -- -
権限があれば一括ダウンロードができます

ソースコード

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