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