結果

問題 No.2204 Palindrome Splitting (No Rearrangement ver.)
ユーザー Moss_Local
提出日時 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`

ソースコード

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

// -*- 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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0