Submission #2119043


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,
}

impl CacheKey {
    fn new(len: usize, last_num_man: u32) -> CacheKey {
        CacheKey {
            len: len,
            last_num_man: last_num_man,
        }
    }
}

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::new(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::new(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
    // 0:45:50 fixed
    // +16min 28sec
}

Submission Info

Submission Time
Task B - Ice Rink Game
User hiratai
Language Rust (1.15.1)
Score 0
Code Size 3308 Byte
Status TLE
Exec Time 2105 ms
Memory 309720 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 500
Status
AC × 3
AC × 15
TLE × 18
Set Name Test Cases
Sample sample_01.txt, sample_02.txt, sample_03.txt
All sample_01.txt, sample_02.txt, sample_03.txt, sample_01.txt, sample_02.txt, sample_03.txt, subtask_1_01.txt, subtask_1_02.txt, subtask_1_03.txt, subtask_1_04.txt, subtask_1_05.txt, subtask_1_06.txt, subtask_1_07.txt, subtask_1_08.txt, subtask_1_09.txt, subtask_1_10.txt, subtask_1_11.txt, subtask_1_12.txt, subtask_1_13.txt, subtask_1_14.txt, subtask_1_15.txt, subtask_1_16.txt, subtask_1_17.txt, subtask_1_18.txt, subtask_1_19.txt, subtask_1_20.txt, subtask_1_21.txt, subtask_1_22.txt, subtask_1_23.txt, subtask_1_24.txt, subtask_1_25.txt, subtask_1_26.txt, subtask_1_27.txt
Case Name Status Exec Time Memory
sample_01.txt AC 2 ms 4352 KB
sample_02.txt AC 2 ms 4352 KB
sample_03.txt AC 2 ms 4352 KB
subtask_1_01.txt AC 2 ms 4352 KB
subtask_1_02.txt AC 2 ms 4352 KB
subtask_1_03.txt AC 2 ms 4352 KB
subtask_1_04.txt AC 2 ms 4352 KB
subtask_1_05.txt AC 2 ms 4352 KB
subtask_1_06.txt AC 37 ms 23420 KB
subtask_1_07.txt AC 10 ms 6396 KB
subtask_1_08.txt AC 2 ms 4352 KB
subtask_1_09.txt TLE 2104 ms 299032 KB
subtask_1_10.txt TLE 2104 ms 299024 KB
subtask_1_11.txt TLE 2104 ms 298840 KB
subtask_1_12.txt TLE 2104 ms 298840 KB
subtask_1_13.txt TLE 2105 ms 309720 KB
subtask_1_14.txt TLE 2104 ms 298840 KB
subtask_1_15.txt TLE 2104 ms 298840 KB
subtask_1_16.txt TLE 2104 ms 299024 KB
subtask_1_17.txt TLE 2104 ms 298840 KB
subtask_1_18.txt TLE 2104 ms 298840 KB
subtask_1_19.txt TLE 2104 ms 298840 KB
subtask_1_20.txt TLE 2104 ms 298840 KB
subtask_1_21.txt TLE 2104 ms 298840 KB
subtask_1_22.txt AC 7 ms 4352 KB
subtask_1_23.txt TLE 2104 ms 299032 KB
subtask_1_24.txt TLE 2104 ms 299032 KB
subtask_1_25.txt TLE 2104 ms 298840 KB
subtask_1_26.txt TLE 2104 ms 299032 KB
subtask_1_27.txt TLE 2104 ms 298840 KB