結果
問題 | No.765 ukuku 2 |
ユーザー |
|
提出日時 | 2019-03-21 18:53:53 |
言語 | Rust (1.83.0 + proconio) |
結果 |
TLE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 8,009 bytes |
コンパイル時間 | 14,386 ms |
コンパイル使用メモリ | 389,148 KB |
実行使用メモリ | 147,820 KB |
最終ジャッジ日時 | 2024-09-19 01:49:55 |
合計ジャッジ時間 | 22,343 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 33 TLE * 1 -- * 14 |
ソースコード
#[allow(unused_imports)]use std::cmp::*;#[allow(unused_imports)]use std::collections::*;use std::io::{Write, BufWriter};// https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8macro_rules! input {(source = $s:expr, $($r:tt)*) => {let mut iter = $s.split_whitespace();let mut next = || { iter.next().unwrap() };input_inner!{next, $($r)*}};($($r:tt)*) => {let stdin = std::io::stdin();let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));let mut next = move || -> String{bytes.by_ref().map(|r|r.unwrap() as char).skip_while(|c|c.is_whitespace()).take_while(|c|!c.is_whitespace()).collect()};input_inner!{next, $($r)*}};}macro_rules! input_inner {($next:expr) => {};($next:expr, ) => {};($next:expr, $var:ident : $t:tt $($r:tt)*) => {let $var = read_value!($next, $t);input_inner!{$next $($r)*}};}macro_rules! read_value {($next:expr, ( $($t:tt),* )) => {( $(read_value!($next, $t)),* )};($next:expr, [ $t:tt ; $len:expr ]) => {(0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()};($next:expr, chars) => {read_value!($next, String).chars().collect::<Vec<char>>()};($next:expr, usize1) => {read_value!($next, usize) - 1};($next:expr, [ $t:tt ]) => {{let len = read_value!($next, usize);(0..len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()}};($next:expr, $t:ty) => {$next().parse::<$t>().expect("Parse error")};}/** Suffix Array by Manber & Myers.* Verified by: AtCoder ARC050 (http://arc050.contest.atcoder.jp/submissions/818912)* Reference: http://mayokoex.hatenablog.com/entry/2016/04/03/145845*/fn create_sa(s: &[char]) -> Vec<usize> {let n = s.len();let mut sa: Vec<usize> = (0 .. n + 1).collect();let mut rank: Vec<usize> = vec![0; n + 1];let mut tmp = vec![0; n + 1];for i in 0 .. n + 1 {rank[i] = if i < n { s[i] as usize + 1 } else { 0_usize };}let mut k = 1;while k <= n {{let key = |i: &usize| {let ri = if i + k <= n { rank[i + k] as i32 } else { -1 };(rank[*i], ri)};sa.sort_by_key(&key);tmp[sa[0]] = 0;for i in 1 .. n + 1 {tmp[sa[i]] = tmp[sa[i - 1]]+ if key(&sa[i - 1]) < key(&sa[i]) { 1 } else { 0 };}}rank.clone_from_slice(&tmp);k *= 2;}return sa;}struct LCP {inv_sa: Vec<usize>,spt: Vec<Vec<usize>>}impl LCP {pub fn new(s: &[char], sa: &[usize]) -> LCP {let n = sa.len() - 1;let mut inv_sa = vec![0; n + 1];for i in 0 .. n + 1 {inv_sa[sa[i]] = i;}let lcp = Self::create_lcp(s, sa);let spt = Self::create_sparse_table(&lcp);LCP {inv_sa: inv_sa,spt: spt,}}fn create_lcp(s: &[char], sa: &[usize]) -> Vec<usize> {let n = s.len();let mut rank = vec![0; n + 1];let mut lcp = vec![0; n];for i in 0 .. n + 1 {rank[sa[i]] = i;}let mut h: usize = 0;lcp[0] = 0;for i in 0 .. n {let j = sa[rank[i] - 1];h = h.saturating_sub(1);while j + h < n && i + h < n {if s[j + h] != s[i + h] {break;}h += 1;}lcp[rank[i] - 1] = h;}return lcp;}fn create_sparse_table(lcp: &[usize]) -> Vec<Vec<usize>> {let n = lcp.len();let mut h: usize = 1;while (1 << h) <= n {h += 1;}let mut st: Vec<Vec<usize>> = vec![Vec::new(); h];st[0] = Vec::from(lcp);for j in 1 .. h {st[j] = vec![0; n + 1 - (1 << j)];for i in 0 .. n + 1 - (1 << j) {st[j][i] = std::cmp::min(st[j - 1][i],st[j - 1][i + 1_usize.wrapping_shl(j as u32 - 1)]);}}return st;}pub fn get_lcp(&self, f: usize, s: usize) -> usize {let f = self.inv_sa[f];let s = self.inv_sa[s];let (f, s) =if f > s {(s, f)} else {(f, s)};assert!(f < s);let usize_size = usize::max_value().count_ones();let diff = usize_size - 1 - (s - f).leading_zeros(); // topmost 1return std::cmp::min(self.spt[diff as usize][f],self.spt[diff as usize][s - 1_usize.wrapping_shl(diff)]);}}// Manacher http://snuke.hatenablog.com/entry/2014/12/02/235837// Verified by https://atcoder.jp/contests/wupc2019/submissions/4540033fn manacher<T: PartialEq>(tmp: &[T]) -> Vec<usize> {let n = tmp.len();let mut r = vec![0; n];{let mut i = 0;let mut j = 0;while i < n {while i >= j && i + j < n && tmp[i - j] == tmp[i + j] {j += 1;}r[i] = j;let mut k = 1;while i >= k && i + k < n && k + r[i - k] < j {r[i + k] = r[i - k];k += 1;}i += k;j -= k;}}r}fn solve() {let out = std::io::stdout();let mut out = BufWriter::new(out.lock());macro_rules! puts {($format:expr) => (write!(out,$format).unwrap());($format:expr, $($args:expr),+) => (write!(out,$format,$($args),*).unwrap())}const DEBUG: bool = false;input! {s_orig: chars,}let n = s_orig.len();let mut s = vec!['.'; 2 * n - 1];for i in 0..n {s[2 * i] = s_orig[i];}let mut revs = s.clone();revs.reverse();let mut srevs = s.clone();srevs.extend_from_slice(&revs);// data structurelet r = manacher(&s);let sa = create_sa(&srevs);let lcp = LCP::new(&srevs, &sa);let mut ma = 1;if DEBUG {eprintln!("r = {:?}", r);}for i in 0..2 * n - 1 {let r = r[i];let mut curma = 0;let base = if 2 * r - 1 == 2 * n - 1 { r - 1 } else { r };curma = max(curma, base);if base != r { continue; }// delete s[i + r], s[i + r + 1]// Want to compare s[0..i - r + 2].reverse() and s[i + r + 1..2 * n - 1]if i + r + 2 <= 2 * n - 1 {let lcp_len = lcp.get_lcp(i + r + 2, 2 * (2 * n - 1) - i + r - 1);let total_len = base + lcp_len;if DEBUG {eprintln!("s[{}] = {} + r = {}, base = {}, total_len = {}", i, s[i], r, base, total_len);}curma = max(curma, total_len);}// delete s[i - r], s[i - r - 1]// Want to compare s[0..i - r - 1].reverse() and s[i + r..2 * n - 1]if i >= r + 1 {let lcp_len = lcp.get_lcp(i + r, 2 * (2 * n - 1) - i + r + 1);let total_len = base + lcp_len;if DEBUG {eprintln!("s[{}] = {} - r = {}, base = {}, total_len = {}", i, s[i], r, base, total_len);}curma = max(curma, total_len);}ma = max(ma, if i % 2 == 0 {(curma + 1) / 2 * 2 - 1 // 1 -> 1, 2 -> 1, 3 -> 3, 4 -> 3, ...} else {curma / 2 * 2 // 1 -> 0, 2 -> 2, 3 -> 2, 4 -> 4, ...});}puts!("{}\n", ma);}fn main() {// In order to avoid potential stack overflow, spawn a new thread.let stack_size = 104_857_600; // 100 MBlet thd = std::thread::Builder::new().stack_size(stack_size);thd.spawn(|| solve()).unwrap().join().unwrap();}