結果
問題 |
No.3082 Make Palindromic Multiple(Judge)
|
ユーザー |
![]() |
提出日時 | 2025-03-29 18:52:48 |
言語 | Rust (1.83.0 + proconio) |
結果 |
AC
|
実行時間 | 1,052 ms / 3,500 ms |
コード長 | 9,283 bytes |
コンパイル時間 | 17,901 ms |
コンパイル使用メモリ | 389,644 KB |
実行使用メモリ | 83,596 KB |
最終ジャッジ日時 | 2025-04-16 13:14:08 |
合計ジャッジ時間 | 53,694 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 73 |
コンパイルメッセージ
warning: fields `sa` and `lcp` are never read --> src/main.rs:118:5 | 116 | pub struct SAString<T> { | -------- fields in this struct 117 | s: Vec<T>, 118 | sa: Vec<usize>, | ^^ 119 | isa: Vec<usize>, 120 | lcp: Vec<usize>, | ^^^ | = note: `#[warn(dead_code)]` on by default
ソースコード
fn main() { input! { n: usize, p: [(bytes, u128); n], } let mut q = p.clone(); q.reverse(); for q in q.iter_mut() { q.0.reverse(); } let ans = if solve(p, q) { "Yes" } else { "No" }; println!("{}", ans); } fn solve(mut p: Vec<(Vec<u8>, u128)>, q: Vec<(Vec<u8>, u128)>) -> bool { let n = p.len(); p.extend(q.into_iter()); let mut s = vec![]; let mut memo = vec![]; for p in p.iter() { memo.push(s.len()); let len = p.0.len(); s.extend(p.0.iter().cloned().cycle().take(2 * len)); } let sa = SAString::new(s); let mut x = (0, 0); let mut y = (n, 0); while x.0 < n && y.0 < p.len() { let z = (x.1 % p[x.0].0.len() as u128) as usize; let w = (y.1 % p[y.0].0.len() as u128) as usize; let l = (memo[x.0] + z, memo[x.0] + z + p[x.0].0.len()); let r = (memo[y.0] + w, memo[y.0] + w + p[y.0].0.len()); let cmp = sa.compare(vec![l, r], vec![r, l]); let lcp = if cmp.0 == std::cmp::Ordering::Equal { let a = &p[x.0]; let b = &p[y.0]; (a.0.len() as u128 * a.1 - x.1).min(b.0.len() as u128 * b.1 - y.1) } else { cmp.1 as u128 }; x.1 += lcp; y.1 += lcp; let mut update = false; let a = &p[x.0]; let b = &p[y.0]; if a.0.len() as u128 * a.1 == x.1 { update = true; x.0 += 1; x.1 = 0; } if b.0.len() as u128 * b.1 == y.1 { update = true; y.0 += 1; y.1 = 0; } if !update { return false; } } true } // ---------- begin input macro ---------- // reference: https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8 #[macro_export] macro_rules! input { (source = $s:expr, $($r:tt)*) => { let mut iter = $s.split_whitespace(); input_inner!{iter, $($r)*} }; ($($r:tt)*) => { let s = { use std::io::Read; let mut s = String::new(); std::io::stdin().read_to_string(&mut s).unwrap(); s }; let mut iter = s.split_whitespace(); input_inner!{iter, $($r)*} }; } #[macro_export] macro_rules! input_inner { ($iter:expr) => {}; ($iter:expr, ) => {}; ($iter:expr, $var:ident : $t:tt $($r:tt)*) => { let $var = read_value!($iter, $t); input_inner!{$iter $($r)*} }; } #[macro_export] macro_rules! read_value { ($iter:expr, ( $($t:tt),* )) => { ( $(read_value!($iter, $t)),* ) }; ($iter:expr, [ $t:tt ; $len:expr ]) => { (0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>() }; ($iter:expr, chars) => { read_value!($iter, String).chars().collect::<Vec<char>>() }; ($iter:expr, bytes) => { read_value!($iter, String).bytes().collect::<Vec<u8>>() }; ($iter:expr, usize1) => { read_value!($iter, usize) - 1 }; ($iter:expr, $t:ty) => { $iter.next().unwrap().parse::<$t>().expect("Parse error") }; } // ---------- end input macro ---------- pub struct SAString<T> { s: Vec<T>, sa: Vec<usize>, isa: Vec<usize>, lcp: Vec<usize>, rmq: RMQ<usize>, } impl<T: Ord> SAString<T> { pub fn new(s: Vec<T>) -> Self { let (sa, isa, lcp) = suffix_array(&s); let rmq = RMQ::new(lcp.clone()); Self { s, sa, isa, lcp, rmq, } } pub fn find_lcp(&self, x: usize, y: usize) -> usize { assert!(x.max(y) < self.s.len()); if x == y { self.s.len() - x.max(y) } else { let a = self.isa[x.min(y)]; let b = self.isa[x.max(y)]; self.rmq.find(a.min(b) + 1, a.max(b) + 1) } } pub fn compare( &self, mut a: Vec<(usize, usize)>, mut b: Vec<(usize, usize)>, ) -> (std::cmp::Ordering, usize) { assert!(a .iter() .chain(b.iter()) .all(|p| p.0 <= p.1 && p.1 <= self.s.len())); a.retain(|p| p.0 < p.1); b.retain(|p| p.0 < p.1); let mut x = 0; let mut y = 0; let mut sum = 0; while x < a.len() && y < b.len() { let a = &mut a[x]; let b = &mut b[y]; let len = (a.1 - a.0).min(b.1 - b.0); let lcp = self.find_lcp(a.0, b.0).min(len); a.0 += lcp; b.0 += lcp; sum += lcp; if a.0 < a.1 && b.0 < b.1 { return (self.s[a.0].cmp(&self.s[b.0]), sum); } if a.0 == a.1 { x += 1; } if b.0 == b.1 { y += 1; } } ((x < a.len()).cmp(&(y < b.len())), sum) } } // O(N (log N)^2) // 文字種によらない // O(N log N) の実装が悪く、log2つの方が早かったので一時的にこちらに更新 // ---------- begin suffix array ---------- fn suffix_array<T: Ord>(s: &[T]) -> (Vec<usize>, Vec<usize>, Vec<usize>) { let n = s.len(); let mut z = s.iter().collect::<Vec<_>>(); z.sort(); z.dedup(); let mut ord = Vec::with_capacity(n); for s in s.iter() { ord.push(z.binary_search(&s).unwrap() as u32 + 1); } let mut z = (0..n).map(|p| ((ord[p], 0), p)).collect::<Vec<_>>(); z.sort_by_key(|p| p.0); let mut len = 1; while len < n { for z in z.iter_mut() { z.0 = (ord[z.1], ord.get(z.1 + len).map_or(0, |p| *p)); } z.sort_by_key(|p| p.0); let mut id = 1; let mut prev = z[0].0; for z in z.iter_mut() { if z.0 != prev { id += 1; prev = z.0; } ord[z.1] = id; } len <<= 1; } let sa = z.into_iter().map(|p| p.1).collect::<Vec<_>>(); let mut isa = vec![0; s.len()]; for (i, sa) in sa.iter().enumerate() { isa[*sa] = i; } let mut lcp = vec![0; s.len()]; let mut h = 0; for i in 0..sa.len() { if isa[i] + 1 < sa.len() { let j = sa[isa[i] + 1]; while i.max(j) + h < sa.len() && s[i + h] == s[j + h] { h += 1; } lcp[isa[i] + 1] = h; if h > 0 { h -= 1; } } } (sa, isa, lcp) } // ---------- end suffix array ---------- pub struct RMQ<T> { data: Vec<T>, table: SparseTable<T>, bit: Vec<usize>, } impl<T> RMQ<T> where T: Ord + Copy, { pub fn new(data: Vec<T>) -> Self { assert!(!data.is_empty()); let mut bit = vec![0; data.len()]; let w = 8 * std::mem::size_of_val(&bit[0]); let mut stack: Vec<usize> = vec![]; let mut table_ini = Vec::with_capacity((data.len() + w - 1) / w); for (bit, data) in bit.chunks_mut(w).zip(data.chunks(w)) { stack.clear(); let mut b = 0; for (i, (bit, d)) in bit.iter_mut().zip(data.iter()).enumerate() { while stack.last().map_or(false, |x| data[*x] > *d) { b ^= 1 << stack.pop().unwrap(); } b |= 1 << i; *bit = b; stack.push(i); } table_ini.push(data[stack[0]]); } let table = SparseTable::new(table_ini); RMQ { data, table, bit } } pub fn find(&self, l: usize, r: usize) -> T { assert!(l < r && r <= self.data.len()); let w = 8 * std::mem::size_of_val(&self.bit[0]); let r = r - 1; let p = l / w; let q = r / w; if p == q { let pos = l + (self.bit[r] >> (l % w)).trailing_zeros() as usize; self.data[pos] } else { let lw = l + (self.bit[p * w + w - 1] >> (l % w)).trailing_zeros() as usize; let rw = q * w + self.bit[r].trailing_zeros() as usize; let mut res = std::cmp::min(self.data[lw], self.data[rw]); if p + 1 < q { res = std::cmp::min(res, self.table.find(p + 1, q)); } res } } } // ---------- begin sparse table (min) ---------- pub struct SparseTable<T> { table: Vec<Vec<T>>, size: usize, } impl<T> SparseTable<T> where T: Ord + Copy, { pub fn new(mut a: Vec<T>) -> Self { assert!(a.len() > 0); let size = a.len(); let mut table = vec![]; let mut w = 1; while w + 1 <= a.len() { let next = a .iter() .zip(a[w..].iter()) .map(|p| std::cmp::min(*p.0, *p.1)) .collect::<Vec<_>>(); table.push(a); a = next; w <<= 1; } table.push(a); SparseTable { table: table, size: size, } } pub fn find(&self, l: usize, r: usize) -> T { assert!(l < r && r <= self.size); let k = 8 * std::mem::size_of::<usize>() - 1 - (r - l).leading_zeros() as usize; let table = &self.table[k]; std::cmp::min(table[l], table[r - (1 << k)]) } } // ---------- end sparse table (min) ----------