Submission #2119032

---

Source Code Expand

#[allow(unused_imports)]
use std::io::*;
#[allow(unused_imports)]
use std::str::*;
#[allow(unused_imports)]
use std::mem::*;
#[allow(unused_imports)]
use std::cmp::*;
#[allow(unused_imports)]
use std::collections::HashSet;
#[allow(unused_imports)]
use std::collections::VecDeque;
#[allow(unused_imports)]
use std::usize;

#[allow(dead_code)]
fn read<T: FromStr>() -> T {
    let mut line = String::new();
    stdin().read_line(&mut line).unwrap();
    line.trim().to_string().parse().ok().unwrap()
}

#[allow(dead_code)]
fn read_cols<T: FromStr>() -> Vec<T> {
    let mut line = String::new();
    stdin().read_line(&mut line).unwrap();

    line.trim()
        .split_whitespace()
        .map(|s| s.parse().ok().unwrap())
        .collect()
}

#[derive(PartialEq, Eq, Hash, Clone, Copy)]
struct CacheKey {
    len: usize,
    last_num_man: u32,
}

fn find_min_num(
    num_man_in_groups: &[u32],
    last_num_man: u32,
    cache: &mut HashSet<CacheKey>,
) -> Option<u32> {
    let len = num_man_in_groups.len();
    let key = CacheKey { len, last_num_man };

    if cache.contains(&key) {
        return None;
    }

    if len == 0 {
        return Some(last_num_man);
    }

    let last = *num_man_in_groups.last().unwrap();
    if last_num_man % last > 0 {
        cache.insert(key);
        return None;
    }

    for last_drop in 0..last {
        let ret = find_min_num(
            num_man_in_groups.get(0..len - 1).unwrap(),
            last_num_man + last_drop,
            cache,
        );
        if let Some(_) = ret {
            return ret;
        }
    }

    cache.insert(key);
    None
}

fn find_max_num(
    num_man_in_groups: &[u32],
    last_num_man: u32,
    cache: &mut HashSet<CacheKey>,
) -> Option<u32> {
    let len = num_man_in_groups.len();

    let key = CacheKey { len, last_num_man };

    if cache.contains(&key) {
        return None;
    }

    if len == 0 {
        return Some(last_num_man);
    }

    let last = *num_man_in_groups.last().unwrap();
    if last_num_man % last > 0 {
        cache.insert(key);
        return None;
    }

    for last_drop in (0..last).rev() {
        let ret = find_max_num(
            num_man_in_groups.get(0..len - 1).unwrap(),
            last_num_man + last_drop,
            cache,
        );
        if let Some(_) = ret {
            return ret;
        }
    }

    cache.insert(key);
    None
}

fn main() {
    // 00:04:00
    let num_rounds = read::<u32>();
    let num_man_in_groups = read_cols::<u32>();
    let last_num_man = 2;

    assert_eq!(num_rounds as usize, num_man_in_groups.len());

    let mut cache = HashSet::new();
    let min = find_min_num(num_man_in_groups.as_slice(), last_num_man, &mut cache);
    if min.is_none() {
        println!("-1");
        return;
    }

    let max = find_max_num(num_man_in_groups.as_slice(), last_num_man, &mut cache);
    println!("{} {}", min.unwrap(), max.unwrap());
    // 0:29:22
    // 25min 22sec
}

Submission Info

Compile Error

error: struct field shorthands are unstable (see issue #37340)
  --> ./Main.rs:46:26
   |
46 |     let key = CacheKey { len, last_num_man };
   |                          ^^^

error: struct field shorthands are unstable (see issue #37340)
  --> ./Main.rs:46:31
   |
46 |     let key = CacheKey { len, last_num_man };
   |                               ^^^^^^^^^^^^

error: struct field shorthands are unstable (see issue #37340)
  --> ./Main.rs:84:26
   |
84 |     let key = CacheKey { len, last_num_man };
   |                          ^^^

error: struct field shorthands are unstable (see issue #37340)
  --> ./Main.rs:84:31
   |
84 |     let key = CacheKey { len, last_num_man };
   |                               ^^^^^^^^^^^^

error: aborting due to 4 previous errors