結果

問題 No.515 典型LCP
ユーザー maspymaspy
提出日時 2020-05-08 20:43:11
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,161 bytes
コンパイル時間 154 ms
コンパイル使用メモリ 82,428 KB
実行使用メモリ 118,760 KB
最終ジャッジ日時 2024-07-03 09:57:20
合計ジャッジ時間 6,332 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 WA -
testcase_02 WA -
testcase_03 AC 39 ms
53,500 KB
testcase_04 AC 38 ms
54,000 KB
testcase_05 AC 202 ms
70,252 KB
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 AC 195 ms
68,640 KB
testcase_16 AC 198 ms
70,076 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from operator import itemgetter

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N = int(readline())
S = read().split()
M, X, D = map(int, S[-3:])
inds, words = zip(*sorted(enumerate(S[:-3], 1), key=itemgetter(1)))

re_index = [0] * (N+1)
for i,x in enumerate(inds):
    re_index[x] = i

def LCP_naive(S, T):
    n = 0
    for s,t in zip(S,T):
        if s != t:
            break
        n += 1
    return n

A = [LCP_naive(S, T) for S, T in zip(words, words[1:])]

N = len(A)

sp = [0] * (20 * N)
for n in range(N):
    sp[n] = A[n]
for i in range(1, 20):
    dx = 1 << i
    if N < dx:
        break
    for n in range(i*N, i*N+N + 1- dx):
        sp[n] = min(sp[n-N], sp[n-N+dx//2])

def lcp(i,j):
    i = re_index[i]
    j = re_index[j]
    items = j - i
    if items == 1:
        return A[i]
    k = (items - 1).bit_length() - 1
    dx = 1 << k
    return min(sp[k*N+i], sp[k*N+j-dx])

answer = 0
MOD = N * (N+1)
for _ in range(M):
    i = X // N + 1
    j = X % N + 1
    if i > j:
        i,j = j,i
    else:
        j += 1
    answer += lcp(i,j)
    X = (X + D) % MOD

print(answer)
0