結果
問題 | No.2204 Palindrome Splitting (No Rearrangement ver.) |
ユーザー |
![]() |
提出日時 | 2023-02-03 21:38:14 |
言語 | Rust (1.83.0 + proconio) |
結果 |
AC
|
実行時間 | 114 ms / 2,000 ms |
コード長 | 9,320 bytes |
コンパイル時間 | 11,996 ms |
コンパイル使用メモリ | 383,212 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-07-02 19:27:27 |
合計ジャッジ時間 | 15,947 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 33 |
コンパイルメッセージ
warning: unnecessary parentheses around type --> src/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 --> src/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 --> src/main.rs:296:9 | 296 | let mut rh = RoLiHa::new(&vu64); | ----^^ | | | help: remove this `mut` warning: variable does not need to be mutable --> src/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 --> src/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 --> src/main.rs:234:17 | 234 | let mut powMemo = vec![0; s.len() + 1]; | ^^^^^^^ help: convert the identifier to snake case: `pow_memo`
ソースコード
// -*- 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 palindromelet 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;}