Submit Info #43647

Problem Lang User Status Time Memory
Assignment Problem rust nebocco AC 248 ms 4.82 MiB

ケース詳細
Name Status Time Memory
example_00 AC 0 ms 0.41 MiB
hand_minus_00 AC 247 ms 4.07 MiB
hand_plus_00 AC 248 ms 3.93 MiB
max_random_00 AC 219 ms 4.82 MiB
max_random_01 AC 222 ms 4.82 MiB
max_random_02 AC 180 ms 4.80 MiB
max_random_03 AC 239 ms 4.82 MiB
max_random_04 AC 213 ms 4.82 MiB
random_00 AC 8 ms 0.95 MiB
random_01 AC 17 ms 1.07 MiB
random_02 AC 2 ms 0.45 MiB
random_03 AC 15 ms 1.07 MiB
random_04 AC 0 ms 0.42 MiB

fn main() { let mut io = IO::new(); input!{ from io, n: usize, a: [[i64; n]; n] } let (v, p) = hungarian(&a); io.println(v); io.iterln(p.into_iter(), " "); } // ------------ libraries start ------------ #[allow(clippy::many_single_char_names)] pub fn hungarian(a: &[Vec<i64>]) -> (i64, Vec<usize>) { let n = a.len(); let (mut p, mut q): (usize, usize); let mut x = vec![n; n]; let mut y = vec![n; n]; assert!(a[0].len() == n, "given matrix is not square: {} rows, {} columns", n, a[0].len()); let mut fx = (0..n).map( |k| *a[k].iter().min().unwrap() ).collect::<Vec<_>>(); let mut fy = vec![0; n]; let mut i = 0; let mut j: usize; while i < n { let mut t = vec![n; n]; let mut s = vec![i; n+1]; p = 0; q = 0; while p <= q && x[i] == n { let mut k = s[p]; j = 0; while j < n && x[i] == n { if fx[k] + fy[j] == a[k][j] && t[j] == n { q += 1; s[q] = y[j]; t[j] = k; if s[q] == n { p = j; while p != n { y[j] = t[j]; k = t[j]; p = x[k]; x[k] = j; j = p; } j = 0; p = 0; } } if j == n { j = 0; } else { j += 1; } } if p == n { p = 0; } else { p += 1; } } if x[i] == n { let mut d = std::i64::MIN; for k in 0..=q { for j in 0..n { if t[j] == n { d = std::cmp::max(d, fx[s[k]] + fy[j] - a[s[k]][j]); } } } for j in 0..n { fy[j] += if t[j] == n { 0 } else { d }; } for k in 0..=q { fx[s[k]] -= d; } } else { i += 1; } } let ret = (0..n).map(|i| a[i][x[i]]).sum::<i64>(); (ret, x) } // ------------ libraries end ------------ // ------------ io module start ------------ use std::io::{stdout, BufWriter, Read, StdoutLock, Write}; pub struct IO { iter: std::str::SplitAsciiWhitespace<'static>, buf: BufWriter<StdoutLock<'static>>, } impl IO { pub fn new() -> Self { let mut input = String::new(); std::io::stdin().read_to_string(&mut input).unwrap(); let input = Box::leak(input.into_boxed_str()); let out = Box::new(stdout()); IO { iter: input.split_ascii_whitespace(), buf: BufWriter::new(Box::leak(out).lock()), } } fn scan_str(&mut self) -> &'static str { self.iter.next().unwrap() } pub fn scan<T: Scan>(&mut self) -> <T as Scan>::Output { <T as Scan>::scan(self) } pub fn scan_vec<T: Scan>(&mut self, n: usize) -> Vec<<T as Scan>::Output> { (0..n).map(|_| self.scan::<T>()).collect() } pub fn print<T: Print>(&mut self, x: T) { <T as Print>::print(self, x); } pub fn println<T: Print>(&mut self, x: T) { self.print(x); self.print("\n"); } pub fn iterln<T: Print, I: Iterator<Item = T>>(&mut self, mut iter: I, delim: &str) { if let Some(v) = iter.next() { self.print(v); for v in iter { self.print(delim); self.print(v); } } self.print("\n"); } pub fn flush(&mut self) { self.buf.flush().unwrap(); } } impl Default for IO { fn default() -> Self { Self::new() } } pub trait Scan { type Output; fn scan(io: &mut IO) -> Self::Output; } macro_rules! impl_scan { ($($t:tt),*) => { $( impl Scan for $t { type Output = Self; fn scan(s: &mut IO) -> Self::Output { s.scan_str().parse().unwrap() } } )* }; } impl_scan!(i16, i32, i64, isize, u16, u32, u64, usize, String, f32, f64); impl Scan for char { type Output = char; fn scan(s: &mut IO) -> Self::Output { s.scan_str().chars().next().unwrap() } } pub enum Bytes {} impl Scan for Bytes { type Output = &'static [u8]; fn scan(s: &mut IO) -> Self::Output { s.scan_str().as_bytes() } } pub enum Chars {} impl Scan for Chars { type Output = Vec<char>; fn scan(s: &mut IO) -> Self::Output { s.scan_str().chars().collect() } } pub enum Usize1 {} impl Scan for Usize1 { type Output = usize; fn scan(s: &mut IO) -> Self::Output { s.scan::<usize>().wrapping_sub(1) } } impl<T: Scan, U: Scan> Scan for (T, U) { type Output = (T::Output, U::Output); fn scan(s: &mut IO) -> Self::Output { (T::scan(s), U::scan(s)) } } impl<T: Scan, U: Scan, V: Scan> Scan for (T, U, V) { type Output = (T::Output, U::Output, V::Output); fn scan(s: &mut IO) -> Self::Output { (T::scan(s), U::scan(s), V::scan(s)) } } impl<T: Scan, U: Scan, V: Scan, W: Scan> Scan for (T, U, V, W) { type Output = (T::Output, U::Output, V::Output, W::Output); fn scan(s: &mut IO) -> Self::Output { (T::scan(s), U::scan(s), V::scan(s), W::scan(s)) } } pub trait Print { fn print(w: &mut IO, x: Self); } macro_rules! impl_print_int { ($($t:ty),*) => { $( impl Print for $t { fn print(w: &mut IO, x: Self) { w.buf.write_all(x.to_string().as_bytes()).unwrap(); } } )* }; } impl_print_int!(i16, i32, i64, isize, u16, u32, u64, usize, f32, f64); impl Print for u8 { fn print(w: &mut IO, x: Self) { w.buf.write_all(&[x]).unwrap(); } } impl Print for &[u8] { fn print(w: &mut IO, x: Self) { w.buf.write_all(x).unwrap(); } } impl Print for &str { fn print(w: &mut IO, x: Self) { w.print(x.as_bytes()); } } impl Print for String { fn print(w: &mut IO, x: Self) { w.print(x.as_bytes()); } } impl<T: Print, U: Print> Print for (T, U) { fn print(w: &mut IO, (x, y): Self) { w.print(x); w.print(" "); w.print(y); } } impl<T: Print, U: Print, V: Print> Print for (T, U, V) { fn print(w: &mut IO, (x, y, z): Self) { w.print(x); w.print(" "); w.print(y); w.print(" "); w.print(z); } } mod neboccoio_macro { #[macro_export] macro_rules! input { (@start $io:tt @read @rest) => {}; (@start $io:tt @read @rest, $($rest: tt)*) => { input!(@start $io @read @rest $($rest)*) }; (@start $io:tt @read @rest mut $($rest:tt)*) => { input!(@start $io @read @mut [mut] @rest $($rest)*) }; (@start $io:tt @read @rest $($rest:tt)*) => { input!(@start $io @read @mut [] @rest $($rest)*) }; (@start $io:tt @read @mut [$($mut:tt)?] @rest $var:tt: [[$kind:tt; $len1:expr]; $len2:expr] $($rest:tt)*) => { let $($mut)* $var = (0..$len2).map(|_| $io.scan_vec::<$kind>($len1)).collect::<Vec<Vec<$kind>>>(); input!(@start $io @read @rest $($rest)*) }; (@start $io:tt @read @mut [$($mut:tt)?] @rest $var:tt: [$kind:tt; $len:expr] $($rest:tt)*) => { let $($mut)* $var = $io.scan_vec::<$kind>($len); input!(@start $io @read @rest $($rest)*) }; (@start $io:tt @read @mut [$($mut:tt)?] @rest $var:tt: $kind:tt $($rest:tt)*) => { let $($mut)* $var = $io.scan::<$kind>(); input!(@start $io @read @rest $($rest)*) }; (from $io:tt $($rest:tt)*) => { input!(@start $io @read @rest $($rest)*) }; } } // ------------ io module end ------------