結果

問題 No.515 典型LCP
コンテスト
ユーザー lam6er
提出日時 2025-04-15 21:00:45
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,641 bytes
コンパイル時間 180 ms
コンパイル使用メモリ 82,976 KB
実行使用メモリ 102,328 KB
最終ジャッジ日時 2025-04-15 21:06:06
合計ジャッジ時間 4,923 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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
    
    base = 911382629
    mod = 10**18 + 3
    
    hash_list = []
    lengths = []
    for s in strings:
        n = len(s)
        lengths.append(n)
        h = [0] * (n + 1)
        current_hash = 0
        for i in range(n):
            current_hash = (current_hash * base + ord(s[i])) % mod
            h[i+1] = current_hash
        hash_list.append(h)
    
    M = int(input[ptr])
    x = int(input[ptr+1])
    d = int(input[ptr+2])
    ptr +=3
    
    sum_ans = 0
    current_x = x
    n = N
    n_minus_1 = n -1
    n_times_n_minus_1 = n * (n-1)
    
    for _ in range(M):
        i = (current_x // n_minus_1) + 1
        j_initial = (current_x % n_minus_1) + 1
        
        if i > j_initial:
            i, j = j_initial, i
        else:
            j = j_initial + 1
        
        a = i -1
        b = j -1
        
        s_hash = hash_list[a]
        t_hash = hash_list[b]
        s_len = lengths[a]
        t_len = lengths[b]
        max_possible = min(s_len, t_len)
        
        low = 0
        high = max_possible
        ans = 0
        while low <= high:
            mid = (low + high) // 2
            if s_hash[mid] == t_hash[mid]:
                ans = mid
                low = mid +1
            else:
                high = mid -1
        
        sum_ans += ans
        
        current_x = (current_x + d) % n_times_n_minus_1
    
    print(sum_ans)

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