結果

問題 No.515 典型LCP
ユーザー gew1fw
提出日時 2025-06-12 18:16:13
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,721 bytes
コンパイル時間 285 ms
コンパイル使用メモリ 82,100 KB
実行使用メモリ 99,636 KB
最終ジャッジ日時 2025-06-12 18:16:56
合計ジャッジ時間 14,439 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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
    M, x, d = map(int, input[ptr:ptr+3])
    ptr += 3

    # Precompute hash arrays for each string
    base = 911382629
    mod = 10**18 + 3
    hash_list = []
    for s in strings:
        h = [0]
        current = 0
        for c in s:
            current = (current * base + ord(c)) % mod
            h.append(current)
        hash_list.append(h)

    total = 0
    n = N
    for _ in range(M):
        q = x
        i_1based = (q // (n-1)) + 1
        j_orig = (q % (n-1)) + 1

        if i_1based > j_orig:
            i = j_orig
            j = i_1based
        else:
            i = i_1based
            j = j_orig + 1

        # Convert to 0-based indices
        i0 = i - 1
        j0 = j - 1

        # Get the two strings and their hash arrays
        s_i = strings[i0]
        s_j = strings[j0]
        h_i = hash_list[i0]
        h_j = hash_list[j0]

        len_i = len(s_i)
        len_j = len(s_j)
        min_len = min(len_i, len_j)

        # Binary search for the maximum LCP
        low = 0
        high = min_len
        ans = 0
        while low <= high:
            mid = (low + high) // 2
            if mid >= len(h_i) or mid >= len(h_j):
                high = mid - 1
                continue
            if h_i[mid] == h_j[mid]:
                ans = mid
                low = mid + 1
            else:
                high = mid - 1

        total += ans

        # Update x for next iteration
        x = (x + d) % (n * (n - 1))

    print(total)

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