結果
問題 |
No.958 たぷりすたべる (回文)
|
ユーザー |
|
提出日時 | 2019-12-21 11:01:01 |
言語 | D (dmd 2.109.1) |
結果 |
AC
|
実行時間 | 161 ms / 2,000 ms |
コード長 | 748 bytes |
コンパイル時間 | 1,510 ms |
コンパイル使用メモリ | 142,648 KB |
実行使用メモリ | 9,020 KB |
最終ジャッジ日時 | 2024-06-22 03:57:00 |
合計ジャッジ時間 | 6,108 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 53 |
ソースコード
import std.stdio; import std.algorithm; int[] manacher(string s) { immutable ulong n = s.length; int[] rad = new int[n]; int i = 0; int k = 0; while (i < n) { while (i-k-1>=0 && i+k+1<n && s[i-k-1]==s[i+k+1]) k++; rad[i] = k; int j = 1; k--; while (i-j>=0 && rad[i-j]<k) { rad[i+j] = rad[i-j]; j++; k--; } i += j; } return rad; } void main() { long N, K, Q; readf("%d %d %d\n", &N, &K, &Q); string S; readf("%s\n", S); int[] rad = manacher(S ~ S ~ S ~ S ~ S); foreach (_; 0..Q) { long A; readf("%d\n", &A); A--; int r = rad[A % N + 2*N]; if (r >= 2*N) { writeln(min(A, N*K-1-A)*2+1); } else { writeln(min(A, N*K-1-A, r)*2+1); } } }