結果

問題 No.2102 [Cherry Alpha *] Conditional Reflection
コンテスト
ユーザー lam6er
提出日時 2025-03-20 20:39:23
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 426 ms / 3,000 ms
コード長 1,342 bytes
コンパイル時間 146 ms
コンパイル使用メモリ 82,476 KB
実行使用メモリ 129,076 KB
最終ジャッジ日時 2025-03-20 20:39:57
合計ジャッジ時間 26,840 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 70
権限があれば一括ダウンロードができます

ソースコード

diff # 

def main():
    import sys
    input = sys.stdin.read().split()
    n = int(input[0])
    lines = input[1:n+1]
    
    base = 911382629
    mod = 10**18 + 3
    max_power = 10**6 + 2
    
    # Precompute powers of the base modulo mod
    p = [1] * (max_power + 1)
    for i in range(1, max_power + 1):
        p[i] = (p[i-1] * base) % mod
    
    seen = set()
    results = []
    
    for s in lines:
        m = len(s)
        h = 0
        for i, c in enumerate(s):
            exponent = m - 1 - i
            h = (h + ord(c) * p[exponent]) % mod
        
        if h in seen:
            results.append("Yes")
            continue
        
        found = False
        for k in range(m - 1):
            if s[k] == s[k+1]:
                continue
            # Swap characters at positions k and k+1
            exponent1 = m - 1 - k
            exponent2 = m - 1 - (k + 1)
            c1 = ord(s[k])
            c2 = ord(s[k + 1])
            delta = ((c2 - c1) * (p[exponent1] - p[exponent2])) % mod
            new_h = (h + delta) % mod
            if new_h in seen:
                found = True
                break
        
        if found:
            results.append("Yes")
        else:
            results.append("No")
        
        seen.add(h)
    
    print('\n'.join(results))

if __name__ == "__main__":
    main()
0