結果

問題 No.2858 Make a Palindrome
ユーザー QiToY
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#![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..n
if 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/034026
pub 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
}
/*
useuseuse
abababa
abaabaaba
abcdcbabcdcbabcdcbabcdcb
abcdcabcdcabcdcabcdcabcdc
cccabb
[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)+l
n*(k-1)+l>=m
n*k>=m+n-l
k = (m+n-l+n-1)/n
aabba
aabbaaabba
*/
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]
};
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0