結果

問題 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]
    };
}
0