結果
問題 |
No.958 たぷりすたべる (回文)
|
ユーザー |
|
提出日時 | 2019-12-21 04:23:19 |
言語 | D (dmd 2.109.1) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,182 bytes |
コンパイル時間 | 753 ms |
コンパイル使用メモリ | 119,492 KB |
実行使用メモリ | 7,248 KB |
最終ジャッジ日時 | 2024-06-22 03:56:29 |
合計ジャッジ時間 | 4,500 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 2 WA * 51 |
ソースコード
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; auto v = A[m.to!int + N]; auto mr = min(m + 1, 3 * N - idx); 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; }