heh
22p2
| -rw-r--r-- | src/main.rs | 63 | ||||
| -rw-r--r-- | src/util.rs | 62 |
2 files changed, 103 insertions, 22 deletions
diff --git a/src/main.rs b/src/main.rs index f7c44c3..c7d70b8 100644 --- a/src/main.rs +++ b/src/main.rs @@ -1,5 +1,11 @@ -#![allow(confusable_idents, uncommon_codepoints, mixed_script_confusables)] +#![allow( + confusable_idents, + uncommon_codepoints, + mixed_script_confusables, + incomplete_features +)] #![feature( + generic_const_exprs, maybe_uninit_uninit_array, inline_const, slice_flatten, @@ -22,16 +28,8 @@ pub use util::prelude::*; #[derive(Copy, Clone)] struct Piece { - a: [u64; 3], - b: [u64; 3], -} - -impl std::fmt::Debug for Piece { - fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { - let [x1, y1, z1] = self.a; - let [x2, y2, z2] = self.b; - write!(f, "[Vector3({x1}, {z1}, {y1}), Vector3({x2}, {z2}, {y2})]") - } + a: [u16; 3], + b: [u16; 3], } pub fn run(i: &str) -> impl Display { @@ -40,13 +38,48 @@ pub fn run(i: &str) -> impl Display { .map(|x| { let (a, b) = x .μ('~') - .mb(|x| x.split(|&x| x == b',').map(読む::完了).Ν::<3>()); + .mb(|x| x.split(|&x| x == b',').map(|x| 読む::完了(x, 10)).Ν::<3>()); pieces.push(Piece { a, b }); }) .Θ(); - println!("{pieces:?}"); - std::process::exit(0); - 0 + + pieces.sort_unstable_by(|a, b| a.a[2].cmp(&b.a[2])); + let mut m: HashMap<(u16, u16), u16> = HashMap::new(); + for p in pieces.iter_mut() { + let a = (p.a[0]..=p.b[0]).flat_map(|x| (p.a[1]..=p.b[1]).map(move |y| (x, y))); + let k = a.clone().map(|x| *m.get(&x).unwrap_or(&0)).max().unwrap() + 1; + for e in a { + m.insert(e, k + p.b[2] - p.a[2]); + } + *p = Piece { + a: p.a.trunc().and(k), + b: p.b.trunc().and(k + p.b[2] - p.a[2]), + }; + } + let mut x = vec![0; pieces.len()]; + for (elem, i) in x.iter_mut().ι::<usize>() { + let mut m: HashMap<(u16, u16), u16> = HashMap::new(); + let mut n = 0; + for (p, j) in pieces.clone().iter_mut().ι::<usize>() { + if j == i { + continue; + } + let a = (p.a[0]..=p.b[0]).flat_map(|x| (p.a[1]..=p.b[1]).map(move |y| (x, y))); + let k = a.clone().map(|x| *m.get(&x).unwrap_or(&0)).max().unwrap() + 1; + for e in a { + m.insert(e, k + p.b[2] - p.a[2]); + } + let z = p.a[2]; + *p = Piece { + a: p.a.trunc().and(k), + b: p.b.trunc().and(k + p.b[2] - p.a[2]), + }; + + n += (k < z) as u16; + } + *elem = n + } + x.into_iter().map(|x| x as u64).sum::<u64>() } fn main() { diff --git a/src/util.rs b/src/util.rs index f20d7d2..91abd99 100644 --- a/src/util.rs +++ b/src/util.rs @@ -13,9 +13,10 @@ pub mod prelude { #[allow(unused_imports)] pub(crate) use super::{bits, dang, leek, mat, shucks, C}; pub use super::{ - even, gcd, gt, lcm, lt, pa, Dir, FilterBy, GreekTools, IntoCombinations, IntoLines, IterͶ, - NumTupleIterTools, ParseIter, Printable, Skip, TakeLine, TupleIterTools2, TupleIterTools3, - TupleUtils, UnifiedTupleUtils, UnsoundUtilities, Widen, 読む, 読む::Ext, Ͷ, Α, Κ, Λ, Μ, + even, gcd, gt, lcm, lt, pa, sort, Dir, FilterBy, GreekTools, IntoCombinations, IntoLines, + IterͶ, NumTupleIterTools, ParseIter, Printable, Push, Skip, TakeLine, Trunc, + TupleIterTools2, TupleIterTools2R, TupleIterTools3, TupleUtils, UnifiedTupleUtils, + UnsoundUtilities, Widen, 読む, 読む::Ext, Ͷ, Α, Κ, Λ, Μ, }; pub use itertools::izip; pub use itertools::Itertools; @@ -717,6 +718,11 @@ pub trait TupleIterTools2<T, U>: Iterator { fn r(self) -> impl Iterator<Item = U>; } +pub trait TupleIterTools2R<T, U>: Iterator { + fn l(self) -> impl Iterator<Item = T>; + fn r(self) -> impl Iterator<Item = U>; +} + pub trait FilterBy<T, U>: Iterator { fn fl(self, f: impl Fn(T) -> bool) -> impl Iterator<Item = (T, U)>; fn fr(self, f: impl Fn(U) -> bool) -> impl Iterator<Item = (T, U)>; @@ -742,7 +748,17 @@ impl<I: Iterator<Item = (u64, u64)>> NumTupleIterTools for I { } } -impl<'a, T: Copy + 'a, U: Copy + 'a, I: Iterator<Item = &'a (T, U)>> TupleIterTools2<T, U> for I { +impl<T, U, I: Iterator<Item = (T, U)>> TupleIterTools2<T, U> for I { + fn l(self) -> impl Iterator<Item = T> { + self.map(|(x, _)| x) + } + + fn r(self) -> impl Iterator<Item = U> { + self.map(|(_, x)| x) + } +} + +impl<'a, T: Copy + 'a, U: Copy + 'a, I: Iterator<Item = &'a (T, U)>> TupleIterTools2R<T, U> for I { fn l(self) -> impl Iterator<Item = T> { self.map(|&(x, _)| x) } @@ -907,10 +923,15 @@ pub mod 読む { } } - pub fn 完了(x: &[u8]) -> u64 { - let mut n = 0; + pub fn 完了< + T: Default + std::ops::Mul<T, Output = T> + std::ops::Add<T, Output = T> + From<u8> + Copy, + >( + x: &[u8], + ten: T, + ) -> T { + let mut n = T::default(); for &byte in x { - n = n * 10 + (byte - b'0') as u64; + n = n * ten + T::from(byte - b'0'); } n } @@ -1155,6 +1176,11 @@ impl Printable for Vec<u8> { } } +pub fn sort<T: Ord>(mut x: Vec<T>) -> Vec<T> { + x.sort_unstable(); + x +} + pub trait TakeLine<'b> { fn take_line<'a>(&'a mut self) -> Option<&'b [u8]>; } @@ -1226,3 +1252,25 @@ impl Skip for &str { *self = &self[n..]; } } + +pub trait Trunc<T, const N: usize> { + /// it does `a[..a.len() - 1].try_into().unwrap()`. + fn trunc(&self) -> [T; N - 1]; +} + +impl<const N: usize, T: Copy> Trunc<T, N> for [T; N] { + fn trunc(&self) -> [T; N - 1] { + self[..N - 1].try_into().unwrap() + } +} + +pub trait Push<T, const N: usize> { + fn and(self, and: T) -> [T; N + 1]; +} + +impl<const N: usize, T> Push<T, N> for [T; N] { + fn and(self, and: T) -> [T; N + 1] { + let mut iter = self.into_iter().chain(std::iter::once(and)); + std::array::from_fn(|_| iter.next().unwrap()) + } +} |