結果

問題 No.2858 Make a Palindrome
ユーザー QiToYQiToY
提出日時 2024-08-25 15:18:13
言語 Rust
(1.77.0)
結果
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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 298 ms
6,812 KB
testcase_01 AC 66 ms
6,940 KB
testcase_02 AC 67 ms
6,940 KB
testcase_03 AC 65 ms
6,944 KB
testcase_04 AC 66 ms
6,940 KB
testcase_05 AC 51 ms
6,940 KB
testcase_06 AC 36 ms
6,940 KB
testcase_07 AC 37 ms
6,944 KB
testcase_08 AC 36 ms
6,940 KB
testcase_09 AC 37 ms
6,944 KB
testcase_10 AC 38 ms
6,944 KB
testcase_11 AC 39 ms
6,940 KB
testcase_12 AC 40 ms
6,944 KB
testcase_13 AC 38 ms
6,940 KB
testcase_14 AC 39 ms
6,944 KB
testcase_15 AC 9 ms
6,940 KB
testcase_16 AC 10 ms
6,940 KB
testcase_17 AC 9 ms
6,944 KB
testcase_18 AC 9 ms
6,944 KB
testcase_19 AC 10 ms
6,944 KB
testcase_20 AC 13 ms
12,396 KB
testcase_21 AC 11 ms
12,596 KB
testcase_22 AC 7 ms
7,552 KB
testcase_23 AC 12 ms
12,268 KB
testcase_24 AC 10 ms
10,908 KB
testcase_25 AC 9 ms
9,972 KB
testcase_26 AC 9 ms
9,580 KB
testcase_27 AC 11 ms
13,704 KB
testcase_28 AC 11 ms
10,660 KB
testcase_29 AC 11 ms
12,896 KB
testcase_30 AC 13 ms
13,872 KB
testcase_31 AC 11 ms
13,820 KB
testcase_32 AC 13 ms
13,848 KB
testcase_33 AC 11 ms
13,888 KB
testcase_34 AC 12 ms
13,980 KB
testcase_35 AC 12 ms
13,912 KB
testcase_36 AC 12 ms
13,936 KB
testcase_37 AC 12 ms
13,812 KB
testcase_38 AC 12 ms
13,856 KB
testcase_39 AC 13 ms
13,884 KB
権限があれば一括ダウンロードができます

ソースコード

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