#836972 (Rust) No.2204 Palindrome Splitting (No Rearrangement ver.)

提出ソース

結果

問題	No.2204 Palindrome Splitting (No Rearrangement ver.)
ユーザー	Moss_Local
提出日時	2023-02-03 21:38:14
言語	Rust (1.77.0)
結果	AC
実行時間	150 ms / 2,000 ms
コード長	9,320 bytes
コンパイル時間	850 ms
コンパイル使用メモリ	159,492 KB
実行使用メモリ	4,384 KB
最終ジャッジ日時	2023-09-15 17:16:39
合計ジャッジ時間	6,546 ms
ジャッジサーバーID （参考情報）	judge15 / judge12

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	1 ms 4,376 KB
testcase_01	AC	1 ms 4,376 KB
testcase_02	AC	1 ms 4,376 KB
testcase_03	AC	86 ms 4,380 KB
testcase_04	AC	21 ms 4,376 KB
testcase_05	AC	12 ms 4,380 KB
testcase_06	AC	147 ms 4,376 KB
testcase_07	AC	133 ms 4,380 KB
testcase_08	AC	119 ms 4,384 KB
testcase_09	AC	125 ms 4,380 KB
testcase_10	AC	147 ms 4,376 KB
testcase_11	AC	119 ms 4,380 KB
testcase_12	AC	146 ms 4,380 KB
testcase_13	AC	150 ms 4,380 KB
testcase_14	AC	147 ms 4,380 KB
testcase_15	AC	135 ms 4,384 KB
testcase_16	AC	56 ms 4,376 KB
testcase_17	AC	74 ms 4,380 KB
testcase_18	AC	147 ms 4,376 KB
testcase_19	AC	147 ms 4,380 KB
testcase_20	AC	147 ms 4,380 KB
testcase_21	AC	147 ms 4,376 KB
testcase_22	AC	147 ms 4,376 KB
testcase_23	AC	147 ms 4,376 KB
testcase_24	AC	147 ms 4,376 KB
testcase_25	AC	147 ms 4,376 KB
testcase_26	AC	147 ms 4,380 KB
testcase_27	AC	96 ms 4,380 KB
testcase_28	AC	147 ms 4,376 KB
testcase_29	AC	147 ms 4,380 KB
testcase_30	AC	1 ms 4,380 KB
testcase_31	AC	1 ms 4,376 KB
testcase_32	AC	124 ms 4,376 KB
testcase_33	AC	147 ms 4,376 KB
testcase_34	AC	1 ms 4,376 KB
testcase_35	AC	125 ms 4,380 KB

権限があれば一括ダウンロードができます

コンパイルメッセージ

warning: unnecessary parentheses around type
  --> Main.rs:64:15
   |
64 | fn readi() -> (i64) {
   |               ^   ^
   |
   = note: `#[warn(unused_parens)]` on by default
help: remove these parentheses
   |
64 - fn readi() -> (i64) {
64 + fn readi() -> i64 {
   |

warning: variable does not need to be mutable
   --> Main.rs:290:9
    |
290 |     let mut v: Vec<char> = read::<String>().chars().map(|c| c as char).collect();
    |         ----^
    |         |
    |         help: remove this `mut`
    |
    = note: `#[warn(unused_mut)]` on by default

warning: variable does not need to be mutable
   --> Main.rs:296:9
    |
296 |     let mut rh = RoLiHa::new(&vu64);
    |         ----^^
    |         |
    |         help: remove this `mut`

warning: variable does not need to be mutable
   --> Main.rs:297:9
    |
297 |     let mut rhrv = RoLiHa::new(&reverse_vu64);
    |         ----^^^^
    |         |
    |         help: remove this `mut`

warning: structure field `powMemo` should have a snake case name
   --> Main.rs:220:5
    |
220 |     powMemo: Vec<u64>,
    |     ^^^^^^^ help: convert the identifier to snake case: `pow_memo`
    |
    = note: `#[warn(non_snake_case)]` on by default

warning: variable `powMemo` should have a snake case name
   --> Main.rs:234:17
    |
234 |         let mut powMemo = vec![0; s.len() + 1];
    |                 ^^^^^^^ help: convert the identifier to snake case: `pow_memo`

warning: 6 warnings emitted

ソースコード

raw source code

// -*- coding:utf-8-unix -*-
// #![feature(map_first_last)]
#![allow(dead_code)]
#![allow(unused_imports)]
#![allow(unused_macros)]
use core::num;
use std::cmp::*;
use std::fmt::*;
use std::hash::*;
use std::*;
use std::{cmp, collections, fmt, io, iter, ops, str};
const INF: i64 = 1223372036854775807;
const UINF: usize = INF as usize;
const LINF: i64 = 2147483647;
const INF128: i128 = 1223372036854775807000000000000;
// const MOD: i64 = 1000000007;
const MOD: i64 = 998244353;
const UMOD: usize = MOD as usize;
const M_PI: f64 = 3.14159265358979323846;
// const MOD: i64 = INF;

use cmp::Ordering::*;
use std::collections::*;
use std::io::stdin;
use std::io::stdout;
use std::io::Write;

macro_rules! p {
    ($x:expr) => {
        println!("{}", $x);
    };
}

macro_rules! d {
    ($x:expr) => {
        println!("{:?}", $x);
    };
}
#[allow(unused_macros)]
pub mod macros {
    macro_rules! min { ($x: expr) => { $x }; ($x: expr, $($xs: expr),+) => {{ let y = macros::min!($($xs),+); std::cmp::min($x, y) } }}
    macro_rules! max { ($x: expr) => { $x }; ($x: expr, $($xs: expr),+) => {{ let y = macros::max!($($xs),+); std::cmp::max($x, y) } }}
    macro_rules! chmin { ($x: expr, $($xs: expr),+) => {{ let y = macros::min!($($xs),+); if $x > y { $x = y; true } else { false } }}}
    macro_rules! chmax { ($x: expr, $($xs: expr),+) => {{ let y = macros::max!($($xs),+); if $x < y { $x = y; true } else { false } }}}
    macro_rules! multi_vec { ($element: expr; ($len: expr, $($lens: expr),*)) => ( vec![macros::multi_vec![$element; ($($lens),*)]; $len] ); ($element: expr; ($len: expr)) => ( vec![$element; $len] ); }
    macro_rules! multi_box_array { ($element: expr; ($len: expr, $($lens: expr),*)) => ( vec![macros::multi_box_array![$element; ($($lens),*)]; $len].into_boxed_slice() ); ($element: expr; ($len: expr)) => ( vec![$element; $len].into_boxed_slice() ); }
    #[allow(unused_imports)]
    pub(super) use {chmax, chmin, max, min, multi_box_array, multi_vec};
}
use macros::*;
fn main() {
    solve();
}

// use str::Chars;
#[allow(dead_code)]
fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}

#[allow(dead_code)]
fn readi() -> (i64) {
    let mut str = String::new();
    let _ = stdin().read_line(&mut str).unwrap();
    let mut iter = str.split_whitespace();
    iter.next().unwrap().parse::<i64>().unwrap()
}

#[allow(dead_code)]
fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>()
        .split_whitespace()
        .map(|e| e.parse().ok().unwrap())
        .collect()
}
#[allow(dead_code)]
fn read_mat<T: std::str::FromStr>(n: u32) -> Vec<Vec<T>> {
    (0..n).map(|_| read_vec()).collect()
}

#[allow(dead_code)]
fn readii() -> (i64, i64) {
    let mut str = String::new();
    let _ = stdin().read_line(&mut str).unwrap();
    let mut iter = str.split_whitespace();
    (
        iter.next().unwrap().parse::<i64>().unwrap(),
        iter.next().unwrap().parse::<i64>().unwrap(),
    )
}

#[allow(dead_code)]
fn readiii() -> (i64, i64, i64) {
    let mut str = String::new();
    let _ = stdin().read_line(&mut str).unwrap();
    let mut iter = str.split_whitespace();
    (
        iter.next().unwrap().parse::<i64>().unwrap(),
        iter.next().unwrap().parse::<i64>().unwrap(),
        iter.next().unwrap().parse::<i64>().unwrap(),
    )
}
#[allow(dead_code)]
fn readuu() -> (usize, usize) {
    let mut str = String::new();
    let _ = stdin().read_line(&mut str).unwrap();
    let mut iter = str.split_whitespace();
    (
        iter.next().unwrap().parse::<usize>().unwrap(),
        iter.next().unwrap().parse::<usize>().unwrap(),
    )
}

#[allow(dead_code)]
fn readff() -> (f64, f64) {
    let mut str = String::new();
    let _ = stdin().read_line(&mut str).unwrap();
    let mut iter = str.split_whitespace();
    (
        iter.next().unwrap().parse::<f64>().unwrap(),
        iter.next().unwrap().parse::<f64>().unwrap(),
    )
}

fn readcc() -> (char, char) {
    let mut str = String::new();
    let _ = stdin().read_line(&mut str).unwrap();
    let mut iter = str.split_whitespace();
    (
        iter.next().unwrap().parse::<char>().unwrap(),
        iter.next().unwrap().parse::<char>().unwrap(),
    )
}

fn readuuu() -> (usize, usize, usize) {
    let mut str = String::new();
    let _ = stdin().read_line(&mut str).unwrap();
    let mut iter = str.split_whitespace();
    (
        iter.next().unwrap().parse::<usize>().unwrap(),
        iter.next().unwrap().parse::<usize>().unwrap(),
        iter.next().unwrap().parse::<usize>().unwrap(),
    )
}
#[allow(dead_code)]
fn readiiii() -> (i64, i64, i64, i64) {
    let mut str = String::new();
    let _ = stdin().read_line(&mut str).unwrap();
    let mut iter = str.split_whitespace();
    (
        iter.next().unwrap().parse::<i64>().unwrap(),
        iter.next().unwrap().parse::<i64>().unwrap(),
        iter.next().unwrap().parse::<i64>().unwrap(),
        iter.next().unwrap().parse::<i64>().unwrap(),
    )
}

#[allow(dead_code)]
fn readuuuu() -> (usize, usize, usize, usize) {
    let mut str = String::new();
    let _ = stdin().read_line(&mut str).unwrap();
    let mut iter = str.split_whitespace();
    (
        iter.next().unwrap().parse::<usize>().unwrap(),
        iter.next().unwrap().parse::<usize>().unwrap(),
        iter.next().unwrap().parse::<usize>().unwrap(),
        iter.next().unwrap().parse::<usize>().unwrap(),
    )
}

#[derive(Debug, Clone)]
#[allow(dead_code)]
pub struct Xorshift {
    seed: u64,
}

impl Xorshift {
    #[allow(dead_code)]
    pub fn new() -> Xorshift {
        Xorshift {
            seed: 0xf0fb588ca2196dac,
        }
    }

    #[allow(dead_code)]
    pub fn with_seed(seed: u64) -> Xorshift {
        Xorshift { seed: seed }
    }

    #[inline(always)]
    #[allow(dead_code)]
    pub fn next(&mut self) -> u64 {
        self.seed = self.seed ^ (self.seed << 13);
        self.seed = self.seed ^ (self.seed >> 7);
        self.seed = self.seed ^ (self.seed << 17);
        self.seed
    }

    #[inline(always)]
    #[allow(dead_code)]
    pub fn rand(&mut self, m: u64) -> u64 {
        self.next() % m
    }

    #[inline(always)]
    #[allow(dead_code)]
    pub fn randf(&mut self) -> f64 {
        use std::mem;
        const UPPER_MASK: u64 = 0x3FF0000000000000;
        const LOWER_MASK: u64 = 0xFFFFFFFFFFFFF;
        let tmp = UPPER_MASK | (self.next() & LOWER_MASK);
        let result: f64 = unsafe { mem::transmute(tmp) };
        result - 1.0
    }
}

struct RoLiHa {
    powMemo: Vec<u64>,
    hash: Vec<u64>,
}
const ROLIHA_MASK30: u64 = (1 << 30) - 1;
const ROLIHA_MASK31: u64 = (1 << 31) - 1;
const ROLIHA_MOD: u64 = (1 << 61) - 1;
const ROLIHA_P: u64 = ROLIHA_MOD * ((1 << 3) - 1);
impl RoLiHa {
    #[doc = "caution: the value should not contain 0"]
    fn new(s: &[u64]) -> Self {
        let mut randgen = Xorshift::new();
        let rand = randgen.rand(std::i64::MAX as u64);
        let base = rand + 129;

        let mut powMemo = vec![0; s.len() + 1];
        powMemo[0] = 1;
        for i in 1..powMemo.len() {
            powMemo[i] = Self::calcmod(Self::mul(powMemo[i - 1], base));
        }

        let mut hash = vec![0; s.len() + 1];
        for i in 0..s.len() {
            hash[i + 1] = Self::calcmod(Self::mul(hash[i], base) + s[i]);
        }

        RoLiHa {
            powMemo: powMemo,
            hash: hash,
        }
    }

    // [l,r)
    pub fn get(&self, l: usize, r: usize) -> u64 {
        return Self::calcmod(
            self.hash[r] + ROLIHA_P - Self::mul(self.hash[l], self.powMemo[r - l]),
        );
    }

    pub fn connect(&self, h1: u64, h2: u64, h2len: usize) -> u64 {
        return Self::calcmod(Self::mul(h1, self.powMemo[h2len]) + h2);
    }

    fn mul(l: u64, r: u64) -> u64 {
        let lu = l >> 31;
        let ld = l & ROLIHA_MASK31;
        let ru = r >> 31;
        let rd = r & ROLIHA_MASK31;
        let middle_bit = ld * ru + lu * rd;
        ((lu * ru) << 1) + ld * rd + ((middle_bit & ROLIHA_MASK30) << 31) + (middle_bit >> 30)
    }

    fn calcmod(x: u64) -> u64 {
        let mut x = (x & ROLIHA_MOD) + (x >> 61);
        if x > ROLIHA_MOD {
            x -= ROLIHA_MOD;
        }
        x
    }
}

// #[test]
// fn test_roliha_get() {
//     let seq: Vec<u64> = "abcabc".chars().map(|c| c as u64).collect();
//     let rh = RoLiHa::new(&seq);
//     assert_eq!(rh.get(0, 3), rh.get(3, 6));
//     assert_ne!(rh.get(0, 4), rh.get(3, 6));
//     assert_ne!(rh.get(0, 3), rh.get(2, 5));
// }

fn solve() {
    let mut v: Vec<char> = read::<String>().chars().map(|c| c as char).collect();
    let mut dp = vec![0; v.len() + 1];

    let vu64 = v.iter().map(|c| *c as u64).collect::<Vec<u64>>();
    let mut reverse_vu64 = vu64.clone();
    reverse_vu64.reverse();
    let mut rh = RoLiHa::new(&vu64);
    let mut rhrv = RoLiHa::new(&reverse_vu64);
    dp[0] = UINF;
    for i in 0..v.len() {
        for j in i..v.len() {
            // check palindrome
            let h1 = rh.get(i, j + 1);
            let h2 = rhrv.get(v.len() - j - 1, v.len() - i);
            if h1 == h2 {
                dp[j + 1] = max(dp[j + 1], min(dp[i], j - i + 1));
            }
        }
        // d!(dp.clone());
    }
    println!("{}", dp[v.len()]);

    return;
}

yukicoder

結果

テストケース

コンパイルメッセージ

ソースコード