結果
問題 | No.765 ukuku 2 |
ユーザー | koba-e964 |
提出日時 | 2019-03-21 18:57:09 |
言語 | Rust (1.77.0 + proconio) |
結果 |
TLE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 7,789 bytes |
コンパイル時間 | 13,756 ms |
コンパイル使用メモリ | 401,996 KB |
実行使用メモリ | 147,560 KB |
最終ジャッジ日時 | 2024-09-19 01:51:10 |
合計ジャッジ時間 | 25,138 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
10,624 KB |
testcase_01 | AC | 1 ms
5,376 KB |
testcase_02 | AC | 1 ms
5,376 KB |
testcase_03 | AC | 1 ms
5,376 KB |
testcase_04 | AC | 1 ms
5,376 KB |
testcase_05 | AC | 1 ms
5,376 KB |
testcase_06 | AC | 1 ms
5,376 KB |
testcase_07 | AC | 1 ms
5,376 KB |
testcase_08 | AC | 1 ms
5,376 KB |
testcase_09 | AC | 1 ms
5,376 KB |
testcase_10 | AC | 1 ms
5,376 KB |
testcase_11 | AC | 1 ms
5,376 KB |
testcase_12 | AC | 1 ms
5,376 KB |
testcase_13 | AC | 1 ms
5,376 KB |
testcase_14 | AC | 1 ms
5,376 KB |
testcase_15 | AC | 1 ms
5,376 KB |
testcase_16 | AC | 1 ms
5,376 KB |
testcase_17 | AC | 1 ms
5,376 KB |
testcase_18 | AC | 1 ms
5,376 KB |
testcase_19 | AC | 1 ms
5,376 KB |
testcase_20 | AC | 1 ms
5,376 KB |
testcase_21 | AC | 1 ms
5,376 KB |
testcase_22 | AC | 1 ms
5,376 KB |
testcase_23 | AC | 1 ms
5,376 KB |
testcase_24 | AC | 1 ms
5,376 KB |
testcase_25 | AC | 1 ms
5,376 KB |
testcase_26 | AC | 1 ms
5,376 KB |
testcase_27 | AC | 1 ms
5,376 KB |
testcase_28 | AC | 2 ms
5,376 KB |
testcase_29 | AC | 1 ms
5,376 KB |
testcase_30 | AC | 2,066 ms
112,480 KB |
testcase_31 | AC | 1,184 ms
109,032 KB |
testcase_32 | AC | 1,609 ms
89,756 KB |
testcase_33 | AC | 591 ms
147,560 KB |
testcase_34 | AC | 587 ms
147,560 KB |
testcase_35 | TLE | - |
testcase_36 | -- | - |
testcase_37 | -- | - |
testcase_38 | -- | - |
testcase_39 | -- | - |
testcase_40 | -- | - |
testcase_41 | -- | - |
testcase_42 | -- | - |
testcase_43 | -- | - |
testcase_44 | -- | - |
testcase_45 | -- | - |
testcase_46 | -- | - |
testcase_47 | -- | - |
testcase_48 | -- | - |
testcase_49 | -- | - |
ソースコード
#[allow(unused_imports)] use std::cmp::*; #[allow(unused_imports)] use std::collections::*; use std::io::{Write, BufWriter}; // https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8 macro_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 1 return 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/4540033 fn 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 structure let 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() { solve(); }