結果

問題 No.515 典型LCP
コンテスト
ユーザー lam6er
提出日時 2025-04-15 21:00:51
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,574 bytes
コンパイル時間 371 ms
コンパイル使用メモリ 82,488 KB
実行使用メモリ 114,820 KB
最終ジャッジ日時 2025-04-15 21:06:20
合計ジャッジ時間 5,024 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 11 TLE * 4
権限があれば一括ダウンロードができます

ソースコード

diff # 

def main():
    import sys
    input = sys.stdin.read().split()
    ptr = 0
    N = int(input[ptr])
    ptr += 1
    strings = []
    for _ in range(N):
        strings.append(input[ptr])
        ptr += 1
    
    # Precompute prefix hashes for each string
    base = 911382629
    mod = 10**18 + 3
    hashes = []
    for s in strings:
        h = [0]
        for c in s:
            h.append((h[-1] * base + (ord(c) - ord('a') + 1)) % mod)
        hashes.append(h)
    
    M = int(input[ptr])
    x = int(input[ptr+1])
    d = int(input[ptr+2])
    ptr +=3
    
    sum_lcp = 0
    current_x = x
    n = N
    mod_val = n * (n -1)
    
    for _ in range(M):
        x_val = current_x
        # Compute i and j
        i = (x_val // (n-1)) + 1
        j_initial = (x_val % (n-1)) + 1
        
        if i > j_initial:
            i, j = j_initial, i
        else:
            j = j_initial + 1
        
        # Get the hash lists
        idx_i = i - 1
        idx_j = j - 1
        h_i = hashes[idx_i]
        h_j = hashes[idx_j]
        len_i = len(h_i) - 1
        len_j = len(h_j) - 1
        max_l = min(len_i, len_j)
        
        # Binary search
        low = 0
        high = max_l
        res = 0
        while low <= high:
            mid = (low + high) // 2
            if h_i[mid] == h_j[mid]:
                res = mid
                low = mid + 1
            else:
                high = mid - 1
        sum_lcp += res
        
        # Update x
        current_x = (x_val + d) % mod_val
    
    print(sum_lcp)

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