heh
Diffstat (limited to 'src/main.rs')
| -rw-r--r-- | src/main.rs | 217 |
1 files changed, 75 insertions, 142 deletions
diff --git a/src/main.rs b/src/main.rs index cd815fb..1e553a3 100644 --- a/src/main.rs +++ b/src/main.rs @@ -1,182 +1,109 @@ #![allow( confusable_idents, uncommon_codepoints, + non_upper_case_globals, internal_features, mixed_script_confusables, + static_mut_refs, incomplete_features )] #![feature( slice_swap_unchecked, generic_const_exprs, + iter_array_chunks, + get_many_mut, maybe_uninit_uninit_array, - inline_const, - slice_flatten, iter_collect_into, let_chains, anonymous_lifetime_in_impl_trait, - unchecked_math, array_windows, slice_take, test, slice_as_chunks, array_chunks, slice_split_once, - core_intrinsics, - byte_slice_trim_ascii + core_intrinsics )] extern crate test; pub mod util; +use atools::prelude::*; +use hinted::HintExt; pub use util::prelude::*; +fn p1(i: &str) -> impl Display { + static mut a: [i32; 1000] = [0; 1000]; + static mut b: [i32; 1000] = [0; 1000]; -pub struct Graph { - pub v: usize, - pub edges: Vec<(usize, usize)>, -} - -pub struct UnionFind { - p: Vec<usize>, - s: Vec<usize>, -} - -impl UnionFind { - pub fn new(size: usize) -> Self { - Self { - s: vec![1; size], - p: (0..size).collect(), - } - } - - fn reset(&mut self) { - self.s.fill(1); - self.p - .iter_mut() - .enumerate() - .for_each(|(idx, val)| *val = idx); - } + let i = i.as_bytes(); + unsafe { + for n in 0..1000 { + let i = C! { &i[n * 14..] }; + let n1 = reading::八( + u64::from_le_bytes(util::nail(C! { &i[..8] })) << 24 | (0x3030303030303030 & !24), + ) as i32; + let n2 = reading::八(u64::from_le_bytes(util::nail(C! { &i[5..]}))) as i32; - pub fn find(&mut self, key: usize) -> usize { - if self.p[key] == key { - return key; + *a.get_unchecked_mut(n) = n1; + *b.get_unchecked_mut(n) = n2; } - let parent = self.find(self.p[key]); - self.p[key] = parent; - parent - } - - pub fn union(&mut self, a: usize, b: usize) -> bool { - let α = self.find(a); - let β = self.find(b); - if α == β { - return false; - } - let a = self.s[α]; - let b = self.s[β]; - if a >= b { - self.s[α] += b; - self.p[β] = α; - } else { - self.s[β] += a; - self.p[α] = β; - } - true - } - - fn group_size(&self, group: usize) -> usize { - self.s[group] + radsort::sort(&mut a); + radsort::sort(&mut b); + a.iter() + .copied() + .zip(b) + .map(|(x, y)| (x - y).abs()) + .sum::<i32>() } } -pub fn karg(graph: &Graph) -> Option<usize> { - let mut v = graph.v; - let mut s = UnionFind::new(v); - while v > 2 { - let i = rand::limit::u64(graph.edges.len() as u64); - let α = s.find(graph.edges[i.nat()].0); - let β = s.find(graph.edges[i.nat()].1); - if α == β { - continue; - } - v -= 1; - s.union(α, β); - } - - let chop = graph - .edges - .iter() - .filter(|&&(src, dest)| s.find(src) != s.find(dest)) - .count(); - - if chop == 3 { - let root = s.find(0); - let size = s.group_size(root); - return Some((graph.v - size) * size); - } - None -} +pub fn run(i: &str) -> impl Display { + static mut a: [u32; 1000] = [0; 1000]; + static mut map: [u32; 100000] = [0; 100000]; + let i = i.as_bytes(); -fn base26([a, b, c]: [u8; 3]) -> u32 { - a.widen().widen() + b.widen().widen() * 26 + c.widen().widen() * 26 * 26 -} + unsafe { + let x = C! { &i[..14] }; + let (x, y) = (reading::all(&x[0..5]), reading::all::<u32>(&x[8..13])); + *a.get_unchecked_mut(0) = x; + *map.get_unchecked_mut(y as usize) += 1; -pub fn run(i: &str) -> impl Display { - let mut z = 0; - let mut n = HashMap::new(); - let mut e: HashMap<u32, HashSet<u32>> = HashMap::new(); - i.行() - .map(|x| { - let (k, v) = x - .μ(':') - .mr(|x| { - x.split(|&x| x == b' ') - .map(<[u8]>::trim_ascii) - .filter(|x| !x.is_empty()) - .map(|x| base26(x.try_into().unwrap())) - .collect_vec() - }) - .ml(<[u8]>::trim_ascii) - .ml(|x| base26(x.try_into().unwrap())); - match n.entry(k) { - Entry::Occupied(_) => {} - Entry::Vacant(x) => { - x.insert(z); - z += 1; - } - } - for j in v { - match e.entry(k) { - Entry::Occupied(x) => { - x.into_mut().insert(j); - } - Entry::Vacant(x) => { - x.insert(HashSet::from_iter([j])); - } - } - match n.entry(j) { - Entry::Occupied(_) => {} - Entry::Vacant(x) => { - x.insert(z); - z += 1; - } - } - } - }) - .Θ(); - let mut edges = vec![]; - for (from, to) in e { - for to in to { - edges.push((n[&from], n[&to])); - } - } - let g = Graph { edges, v: z }; - loop { - if let Some(x) = karg(&g) { - return x; + for n in 1..1000 { + let x = util::reading::八( + u64::from_le_bytes(util::nail::<8>(i.get_unchecked(n * 14 - 3..))) + & 0xffffffffff000000, + ); + let y = util::reading::八(u64::from_le_bytes(util::nail::<8>( + i.get_unchecked(n * 14 + 5..), + ))); + *a.get_unchecked_mut(n) = x as u32; + *map.get_unchecked_mut(y as usize) += 1; } + a.iter() + .copied() + .map(|x| x * map.get_unchecked(x as usize)) + .sum::<u32>() } + + // let (mut a, b) = i + // .行() + // .map(|x| x.κ::<u32>().carr().tuple()) + // .collect::<(Vec<_>, Vec<u32>)>(); + // let mut map = HashMap::<u32, u32>::default(); + // for elem in b { + // map.entry(elem).and_modify(|x| *x += 1).or_insert(1); + // } + // a.sort_unstable(); + // a.iter().map(|x| x * map.get(x).unwrap_or(&0)).sum::<u32>() } fn main() { - let i = include_str!("inp.txt").trim(); + // let mut s = String::new(); + // for i in 0..1280 { + let i = include_str!("inp.txt"); + // s.push_str(i); + // } + // std::fs::write("src/inp.txt", s); + println!("{}", p1(i)); + // println!("{}", experiment(i)); println!("{}", run(i)); } @@ -185,3 +112,9 @@ fn bench(b: &mut test::Bencher) { let i = boxd(include_str!("inp.txt").trim()); b.iter(|| run(i)); } + +#[bench] +fn bench2(b: &mut test::Bencher) { + let i = boxd(include_str!("inp.txt").trim()); + b.iter(|| p1(i)); +} |