結果
問題 | No.958 たぷりすたべる (回文) |
ユーザー |
|
提出日時 | 2019-12-21 04:25:01 |
言語 | D (dmd 2.109.1) |
結果 |
AC
|
実行時間 | 106 ms / 2,000 ms |
コード長 | 1,180 bytes |
コンパイル時間 | 717 ms |
コンパイル使用メモリ | 118,916 KB |
実行使用メモリ | 6,948 KB |
最終ジャッジ日時 | 2024-06-22 03:56:52 |
合計ジャッジ時間 | 4,625 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 53 |
ソースコード
import std.stdio, std.array, std.string, std.conv, std.algorithm; import std.typecons, std.range, std.random, std.math, std.container; import std.numeric, std.bigint, core.bitop, core.stdc.stdio; void main() { auto s = readln.split.map!(to!int); auto N = s[0]; auto K = s[1].to!long; auto Q = s[2]; auto S = readln.chomp; auto T = S ~ S ~ S; auto A = manacher(T); auto L = K * N; foreach (_; 0..Q) { auto idx = readln.chomp.to!long - 1; auto rest = min(idx + 1, L - idx); auto m = idx % N + N; auto v = A[m.to!int]; auto mr = min(m + 1, 3 * N - m); long ans; if (v == mr) { ans = rest; } else { ans = v; } ans = min(ans, rest); writeln(ans * 2 - 1); } } int[] manacher(string s) { int n = s.length.to!int; auto ret = new int[](n); for (int i = 0, j = 0; i < n; ) { while (i - j >= 0 && i + j < n && s[i - j] == s[i + j]) ++j; ret[i] = j; int k = 1; while (i - k >= 0 && i + k < n && k + ret[i - k] < j) ret[i + k] = ret[i - k], ++k; i += k; j -= k; } return ret; }