結果
問題 | No.1018 suffixsuffixsuffix |
ユーザー | maspy |
提出日時 | 2023-06-30 14:10:49 |
言語 | Python3 (3.12.2 + numpy 1.26.4 + scipy 1.12.0) |
結果 |
AC
|
実行時間 | 787 ms / 2,000 ms |
コード長 | 2,221 bytes |
コンパイル時間 | 75 ms |
コンパイル使用メモリ | 11,084 KB |
実行使用メモリ | 54,288 KB |
最終ジャッジ日時 | 2023-09-21 07:40:18 |
合計ジャッジ時間 | 21,995 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge11 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 130 ms
30,100 KB |
testcase_01 | AC | 131 ms
30,064 KB |
testcase_02 | AC | 137 ms
30,020 KB |
testcase_03 | AC | 131 ms
30,112 KB |
testcase_04 | AC | 134 ms
30,080 KB |
testcase_05 | AC | 132 ms
30,208 KB |
testcase_06 | AC | 132 ms
30,024 KB |
testcase_07 | AC | 130 ms
30,028 KB |
testcase_08 | AC | 131 ms
30,160 KB |
testcase_09 | AC | 454 ms
52,476 KB |
testcase_10 | AC | 446 ms
53,168 KB |
testcase_11 | AC | 463 ms
54,288 KB |
testcase_12 | AC | 456 ms
52,916 KB |
testcase_13 | AC | 453 ms
52,772 KB |
testcase_14 | AC | 695 ms
51,700 KB |
testcase_15 | AC | 706 ms
51,832 KB |
testcase_16 | AC | 754 ms
52,620 KB |
testcase_17 | AC | 727 ms
52,052 KB |
testcase_18 | AC | 734 ms
51,640 KB |
testcase_19 | AC | 245 ms
44,812 KB |
testcase_20 | AC | 247 ms
45,308 KB |
testcase_21 | AC | 245 ms
45,148 KB |
testcase_22 | AC | 256 ms
45,608 KB |
testcase_23 | AC | 255 ms
45,872 KB |
testcase_24 | AC | 759 ms
51,548 KB |
testcase_25 | AC | 772 ms
53,264 KB |
testcase_26 | AC | 710 ms
50,984 KB |
testcase_27 | AC | 735 ms
52,048 KB |
testcase_28 | AC | 733 ms
51,576 KB |
testcase_29 | AC | 318 ms
45,896 KB |
testcase_30 | AC | 326 ms
46,796 KB |
testcase_31 | AC | 318 ms
46,648 KB |
testcase_32 | AC | 323 ms
47,044 KB |
testcase_33 | AC | 315 ms
45,504 KB |
testcase_34 | AC | 131 ms
29,896 KB |
testcase_35 | AC | 253 ms
46,024 KB |
testcase_36 | AC | 325 ms
45,720 KB |
testcase_37 | AC | 787 ms
53,068 KB |
ソースコード
#!/usr/local/bin/python3.8 import sys read = sys.stdin.read readline = sys.stdin.readline readlines = sys.stdin.readlines import numpy as np N, M, Q = map(int, readline().split()) S = readline().rstrip() K = tuple(map(int, read().split())) def suffix_array(S): N = len(S) n = 1 key = np.array([ord(x) for x in S]) for _ in range(N.bit_length() + 1): ind = key.argsort() key_sort = key[ind] # 同じ数はまとめる cls = np.ones(N, np.int64) cls[1:] = (key_sort[1:] != key_sort[:-1]) np.cumsum(cls, out=cls) rank = np.empty_like(cls) rank[ind] = cls if n >= N: break n *= 2 key = rank * (cls[-1] + 10) key[:-n // 2] += rank[n // 2:] return ind, rank - 1 def prime_table(N): is_prime = np.zeros(N + 1, np.bool_) is_prime[2] = 1 is_prime[3::2] = 1 for p in range(3, N, 2): if p * p >= N: break if is_prime[p]: is_prime[p * p:: p + p] = 0 primes = np.where(is_prime)[0] return is_prime, primes is_prime, primes = prime_table(10 ** 5 + 10) # repeated 対策 def to_standard_form(S, M): for p in primes: if p > len(S): break while True: L = len(S) if L % p != 0: break dx = L // p repeated = True for i in range(1, p): if S[i * dx: i * dx + dx] != S[:dx]: repeated = False break if not repeated: break S = S[:dx] M *= p return S, M S, M = to_standard_form(S, M) if M == 1: SA, ISA = suffix_array(S) K = np.array(K) answers = 1 + SA[K - 1] print(' '.join(answers.astype(str))) exit() SA, ISA = suffix_array(S * 2) # 長さを並べる N = len(S) SA = (N * 2 - SA) answer = [0] * Q i = 0 ind = 1 for x in SA.tolist(): if x <= N: n = 1 else: n = M - 1 while i < Q and K[i] < ind + n: answer[i] = N * (M - K[i] + ind) + 1 - x i += 1 ind += n # 長さを持ったので、インデックスに戻す print(' '.join(map(str, answer)))