結果
問題 | No.2858 Make a Palindrome |
ユーザー |
![]() |
提出日時 | 2024-08-25 15:18:13 |
言語 | Rust (1.83.0 + proconio) |
結果 |
AC
|
実行時間 | 298 ms / 3,000 ms |
コード長 | 2,817 bytes |
コンパイル時間 | 11,874 ms |
コンパイル使用メモリ | 401,872 KB |
実行使用メモリ | 13,980 KB |
最終ジャッジ日時 | 2024-08-25 15:18:30 |
合計ジャッジ時間 | 15,206 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 40 |
ソースコード
#![allow(unused_imports)]fn main() {input! {t: usize,}'task: for _ in 0..t {input! {n: usize, m: usize,s: Chars,}let man = manacher(&s);// eprintln!("{man:?}");for &ma in &man {if ma >= m {println!("1");continue 'task;}}{let s = s.repeat(2);let man = manacher(&s);for &ma in &man {if ma >= m {println!("2");continue 'task;}}}let mut l = 0;for i in 0..n {// 0..i and i..nif man[i] == i && man[i + n] == n - i {chmax!(l, i.max(n - i));}}if l == 0 {println!("-1");} else {println!("{}", (m + n - l + n - 1) / n);}}}// https://ngtkana.hatenablog.com/entry/2024/03/17/034026pub fn manacher<T: Eq>(s: &[T]) -> Vec<usize> {let n = s.len();let mut a = vec![0; 2 * n + 1];let mut i = 1;let mut j = 1;while i <= 2 * n {// 1. 伸ばせるだけ伸ばすwhile j < i && i + j < 2 * n && s[(i - j) / 2 - 1] == s[(i + j) / 2] {j += 2;}a[i] = j;// ※ 空区間になった場合は例外的な対応が必要if j == 0 {i += 1;j = 1;continue;}// 2. 境界に達しない限り、回文配列を書き写すlet mut k = 1;while k <= i && k + a[i - k] < j {a[i + k] = a[i - k];k += 1;}// 3. 境界に達したら現在の回文区間を覚えて 1 に戻るi += k;j -= k;}a}/*useuseuseabababaabaabaabaabcdcbabcdcbabcdcbabcdcbabcdcabcdcabcdcabcdcabcdccccabb[p0][p1][p2]=> No[p0][p1]=> Yes[p0][p1] .. [p0][p1] (k times)len is n*(k-1) + [p0].len().max([p1].len()) =: n*(k-1)+ln*(k-1)+l>=mn*k>=m+n-lk = (m+n-l+n-1)/naabbaaabbaaabba*/use proconio::{input, marker::*};use std::{cmp::Reverse, collections::*};#[macro_export]macro_rules! chmax {($a:expr, $b:expr) => {{let tmp = $b;if $a < tmp {$a = tmp;true} else {false}}};}#[macro_export]macro_rules! chmin {($a:expr, $b:expr) => {{let tmp = $b;if $a > tmp {$a = tmp;true} else {false}}};}#[macro_export]/// mvec![]macro_rules! mvec {($val:expr; ()) => {$val};($val:expr; ($size:expr $(,$rest:expr)*)) => {vec![mvec![$val; ($($rest),*)]; $size]};}