結果
| 問題 | No.2179 Planet Traveler |
| ユーザー |
 atcoder8
|
| 提出日時 | 2023-01-13 02:03:57 |
| 言語 | Rust (1.77.0) |
| 結果 |
AC
|
| 実行時間 | 182 ms / 3,000 ms |
| コード長 | 24,416 bytes |
| コンパイル時間 | 1,236 ms |
| コンパイル使用メモリ | 158,768 KB |
| 実行使用メモリ | 14,280 KB |
| 最終ジャッジ日時 | 2023-08-25 11:15:14 |
| 合計ジャッジ時間 | 5,739 ms |
|
ジャッジサーバーID （参考情報） |
judge11 / judge13 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 1 ms
4,380 KB |
| testcase_01 | AC | 1 ms
4,380 KB |
| testcase_02 | AC | 1 ms
4,376 KB |
| testcase_03 | AC | 1 ms
4,376 KB |
| testcase_04 | AC | 1 ms
4,380 KB |
| testcase_05 | AC | 1 ms
4,376 KB |
| testcase_06 | AC | 1 ms
4,376 KB |
| testcase_07 | AC | 1 ms
4,376 KB |
| testcase_08 | AC | 1 ms
4,380 KB |
| testcase_09 | AC | 2 ms
4,380 KB |
| testcase_10 | AC | 2 ms
4,376 KB |
| testcase_11 | AC | 126 ms
14,280 KB |
| testcase_12 | AC | 182 ms
14,176 KB |
| testcase_13 | AC | 130 ms
13,924 KB |
| testcase_14 | AC | 70 ms
14,088 KB |
| testcase_15 | AC | 70 ms
14,020 KB |
| testcase_16 | AC | 67 ms
14,112 KB |
| testcase_17 | AC | 145 ms
13,644 KB |
| testcase_18 | AC | 145 ms
13,848 KB |
| testcase_19 | AC | 144 ms
13,748 KB |
| testcase_20 | AC | 23 ms
4,376 KB |
| testcase_21 | AC | 151 ms
13,072 KB |
| testcase_22 | AC | 99 ms
10,320 KB |
| testcase_23 | AC | 76 ms
9,404 KB |
| testcase_24 | AC | 115 ms
12,100 KB |
| testcase_25 | AC | 87 ms
10,540 KB |
| testcase_26 | AC | 124 ms
12,684 KB |
| testcase_27 | AC | 21 ms
4,376 KB |
| testcase_28 | AC | 58 ms
8,468 KB |
| testcase_29 | AC | 119 ms
11,816 KB |
ソースコード
use std::collections::VecDeque;
use crate::atcoder8_library::binary_search::BinarySearchWithI64;
fn main() {
let n = {
let mut line = String::new();
std::io::stdin().read_line(&mut line).unwrap();
line.trim().parse::<usize>().unwrap()
};
let mut xyt = Vec::new();
for _ in 0..n {
xyt.push({
let mut line = String::new();
std::io::stdin().read_line(&mut line).unwrap();
let mut iter = line.split_whitespace();
(
iter.next().unwrap().parse::<i64>().unwrap(),
iter.next().unwrap().parse::<i64>().unwrap(),
iter.next().unwrap().parse::<usize>().unwrap(),
)
});
}
let mut ceil_sq_dist_mat = vec![vec![0; n]; n];
for i in 0..n {
let (x1, y1, t1) = xyt[i];
let sq_r1 = x1.pow(2) + y1.pow(2);
for j in (i + 1)..n {
let (x2, y2, t2) = xyt[j];
if t1 == t2 {
let sq_dist = calc_sq_euclid_dist((x1, y1), (x2, y2));
ceil_sq_dist_mat[i][j] = sq_dist;
ceil_sq_dist_mat[j][i] = sq_dist;
} else {
// (r1 - r2)**2 = r1**2 - 2*r1*r2 + r2**2 = sq_r1 + sq_r2 - sqrt(4*sq_r1*sq_r2)
let sq_r2 = x2.pow(2) + y2.pow(2);
let ceil_sqrt = calc_floor_sqrt(4 * sq_r1 * sq_r2);
let ceil_sq_dist = sq_r1 + sq_r2 - ceil_sqrt;
ceil_sq_dist_mat[i][j] = ceil_sq_dist;
ceil_sq_dist_mat[j][i] = ceil_sq_dist;
}
}
}
let is_ok = |s: i64| {
let mut graph = vec![vec![]; n];
for i in 0..n {
for j in (i + 1)..n {
if s >= ceil_sq_dist_mat[i][j] {
graph[i].push(j);
graph[j].push(i);
}
}
}
let mut que = VecDeque::from(vec![0]);
let mut visited = vec![false; n];
visited[0] = true;
while let Some(cur) = que.pop_front() {
for &next in &graph[cur] {
if visited[next] {
continue;
}
visited[next] = true;
que.push_back(next);
}
}
visited[n - 1]
};
let ans = (0_i64..=3_200_000_000).binary_search(is_ok, false).unwrap();
println!("{}", ans);
}
fn calc_sq_euclid_dist(coord1: (i64, i64), coord2: (i64, i64)) -> i64 {
(coord1.0 - coord2.0).pow(2) + (coord1.1 - coord2.1).pow(2)
}
fn calc_floor_sqrt(n: i64) -> i64 {
assert!(n >= 0);
(0..=n.min(2_000_000_000))
.binary_search(|x| x.pow(2) <= n, true)
.unwrap()
}
pub mod atcoder8_library {
pub mod binary_search {
//! Implements binary search for range represented by the Rust's built-in range type.
use std::ops::{
Range, RangeBounds, RangeFrom, RangeFull, RangeInclusive, RangeTo, RangeToInclusive,
};
macro_rules! impl_binary_search_with_integer {
($int_type: ident, $fn_name_for_inc: ident, $fn_name_for_dec: ident, $fn_name: ident, $trait_name: ident) => {
fn $fn_name_for_inc<R, F>(rng: R, mut is_ok: F) -> Option<$int_type>
where
R: RangeBounds<$int_type>,
F: FnMut($int_type) -> bool,
{
let mut left = match rng.start_bound() {
std::ops::Bound::Included(&start) => start,
std::ops::Bound::Excluded(&start) => {
if start == std::$int_type::MAX {
return None;
}
start + 1
}
std::ops::Bound::Unbounded => std::$int_type::MIN,
};
let mut right = match rng.end_bound() {
std::ops::Bound::Included(&end) => {
if end == std::$int_type::MAX {
if !is_ok(end) {
return None;
}
end
} else {
end + 1
}
}
std::ops::Bound::Excluded(&end) => end,
std::ops::Bound::Unbounded => std::$int_type::MAX,
};
if left >= right {
return None;
}
if is_ok(left) {
return Some(left);
}
if left + 1 == right || !is_ok(right - 1) {
return None;
}
while right - left > 1 {
let mid = left + (right - left) / 2;
if is_ok(mid) {
right = mid;
} else {
left = mid;
}
}
Some(right)
}
fn $fn_name_for_dec<R, F>(rng: R, mut is_ok: F) -> Option<$int_type>
where
R: RangeBounds<$int_type>,
F: FnMut($int_type) -> bool,
{
let mut left = match rng.start_bound() {
std::ops::Bound::Included(&start) => start,
std::ops::Bound::Excluded(&start) => {
if start == std::$int_type::MAX {
return None;
}
start + 1
}
std::ops::Bound::Unbounded => std::$int_type::MIN,
};
let mut right = match rng.end_bound() {
std::ops::Bound::Included(&end) => {
if end == std::$int_type::MAX {
if is_ok(end) {
return Some(end);
}
end
} else {
end + 1
}
}
std::ops::Bound::Excluded(&end) => end,
std::ops::Bound::Unbounded => std::$int_type::MAX,
};
if left >= right {
return None;
}
if is_ok(right - 1) {
return Some(right - 1);
}
if left + 1 == right || !is_ok(left) {
return None;
}
while right - left > 1 {
let mid = left + (right - left) / 2;
if is_ok(mid) {
left = mid;
} else {
right = mid;
}
}
Some(left)
}
/// If `is_ok` is monotonically increasing, returns the smallest integer `x`
/// that satisfies `is_ok(x) = true` as the value of `Some`.
///
/// If `is_ok` is monotonically decreasing, returns the largest integer `x`
/// that satisfies `is_ok(x) = true` as the value of `Some`.
///
/// Returns `None` if no such integer exists in both of the above cases.
///
/// # Arguments
///
/// * `rng` - Domain of function `is_ok`.
/// * `is_ok` - Monotonic function.
/// * `dec` - Represents that `is_ok` is a monotonically decreasing function if true,
/// or a monotonically increasing function if false.
///
/// # Examples
///
/// ```
/// use atcoder8_library::binary_search::binary_search_with_i64;
///
/// let is_ok = |x: i64| { x.pow(2) >= 400 };
/// assert_eq!(binary_search_with_i64(0..100, is_ok, false), Some(20));
///
/// let is_ok = |x: i64| { x.pow(2) >= 400 };
/// assert_eq!(binary_search_with_i64(0..10, is_ok, false), None);
///
/// let is_ok = |x: i64| { x.pow(3) < -8000 };
/// assert_eq!(binary_search_with_i64(-100..0, is_ok, true), Some(-21));
/// ```
pub fn $fn_name<R, F>(rng: R, is_ok: F, dec: bool) -> Option<$int_type>
where
R: RangeBounds<$int_type>,
F: FnMut($int_type) -> bool,
{
if dec {
$fn_name_for_dec(rng, is_ok)
} else {
$fn_name_for_inc(rng, is_ok)
}
}
pub trait $trait_name: Sized + RangeBounds<$int_type> {
/// Performs a binary search on the domain specified by the Rust's built-in range type.
///
/// If `is_ok` is monotonically increasing, returns the smallest integer `x`
/// that satisfies `is_ok(x) = true` as the value of `Some`.
///
/// If `is_ok` is monotonically decreasing, returns the largest integer `x`
/// that satisfies `is_ok(x) = true` as the value of `Some`.
///
/// Returns `None` if no such integer exists in both of the above cases.
///
/// # Arguments
///
/// * `is_ok` - Monotonic function.
/// * `dec` - Represents that `is_ok` is a monotonically decreasing function if true,
/// or a monotonically increasing function if false.
///
/// # Examples
///
/// ```
/// use atcoder8_library::binary_search::BinarySearchWithI64;
///
/// let is_ok = |x: i64| { x.pow(2) >= 400 };
/// assert_eq!((0..100).binary_search(is_ok, false), Some(20));
///
/// let is_ok = |x: i64| { x.pow(2) >= 400 };
/// assert_eq!((0..10).binary_search(is_ok, false), None);
///
/// let is_ok = |x: i64| { x.pow(3) < -8000 };
/// assert_eq!((-100..0).binary_search(is_ok, true), Some(-21));
/// ```
fn binary_search<F>(self, is_ok: F, dec: bool) -> Option<$int_type>
where
F: FnMut($int_type) -> bool,
{
$fn_name(self, is_ok, dec)
}
}
impl $trait_name for RangeFull {}
impl $trait_name for RangeTo<$int_type> {}
impl $trait_name for RangeToInclusive<$int_type> {}
impl $trait_name for RangeFrom<$int_type> {}
impl $trait_name for Range<$int_type> {}
impl $trait_name for RangeInclusive<$int_type> {}
};
}
impl_binary_search_with_integer!(
i8,
binary_search_with_i8_for_inc,
binary_search_with_i8_for_dec,
binary_search_with_i8,
BinarySearchWithI8
);
impl_binary_search_with_integer!(
i16,
binary_search_with_i16_for_inc,
binary_search_with_i16_for_dec,
binary_search_with_i16,
BinarySearchWithI16
);
impl_binary_search_with_integer!(
i32,
binary_search_with_i32_for_inc,
binary_search_with_i32_for_dec,
binary_search_with_i32,
BinarySearchWithI32
);
impl_binary_search_with_integer!(
i64,
binary_search_with_i64_for_inc,
binary_search_with_i64_for_dec,
binary_search_with_i64,
BinarySearchWithI64
);
impl_binary_search_with_integer!(
i128,
binary_search_with_i128_for_inc,
binary_search_with_i128_for_dec,
binary_search_with_i128,
BinarySearchWithI128
);
impl_binary_search_with_integer!(
isize,
binary_search_with_isize_for_inc,
binary_search_with_isize_for_dec,
binary_search_with_isize,
BinarySearchWithIsize
);
impl_binary_search_with_integer!(
u8,
binary_search_with_u8_for_inc,
binary_search_with_u8_for_dec,
binary_search_with_u8,
BinarySearchWithU8
);
impl_binary_search_with_integer!(
u16,
binary_search_with_u16_for_inc,
binary_search_with_u16_for_dec,
binary_search_with_u16,
BinarySearchWithU16
);
impl_binary_search_with_integer!(
u32,
binary_search_with_u32_for_inc,
binary_search_with_u32_for_dec,
binary_search_with_u32,
BinarySearchWithU32
);
impl_binary_search_with_integer!(
u64,
binary_search_with_u64_for_inc,
binary_search_with_u64_for_dec,
binary_search_with_u64,
BinarySearchWithU64
);
impl_binary_search_with_integer!(
u128,
binary_search_with_u128_for_inc,
binary_search_with_u128_for_dec,
binary_search_with_u128,
BinarySearchWithU128
);
impl_binary_search_with_integer!(
usize,
binary_search_with_usize_for_inc,
binary_search_with_usize_for_dec,
binary_search_with_usize,
BinarySearchWithUsize
);
macro_rules! impl_binary_search_with_float {
($float_type: ident, $fn_name_for_inc: ident, $fn_name_for_dec: ident, $fn_name: ident, $trait_name: ident) => {
fn $fn_name_for_inc<R, F>(
rng: R,
mut is_ok: F,
eps: $float_type,
) -> Option<$float_type>
where
R: RangeBounds<$float_type>,
F: FnMut($float_type) -> bool,
{
let mut left = match rng.start_bound() {
std::ops::Bound::Included(&start) => start,
std::ops::Bound::Excluded(&start) => start,
std::ops::Bound::Unbounded => std::$float_type::MIN,
};
let mut right = match rng.end_bound() {
std::ops::Bound::Included(&end) => end,
std::ops::Bound::Excluded(&end) => end,
std::ops::Bound::Unbounded => std::$float_type::MAX,
};
assert!(
eps > 0.0,
"Allowable margin of error must be a positive number."
);
if left >= right {
return None;
}
if is_ok(left) {
return Some(left);
}
if !is_ok(right) {
return None;
}
while right - left > eps {
let mid = right - (right - left) / 2.0;
if mid <= left || right <= mid {
return None;
}
if is_ok(mid) {
right = mid;
} else {
left = mid;
}
}
Some(right)
}
fn $fn_name_for_dec<R, F>(
rng: R,
mut is_ok: F,
eps: $float_type,
) -> Option<$float_type>
where
R: RangeBounds<$float_type>,
F: FnMut($float_type) -> bool,
{
let mut left = match rng.start_bound() {
std::ops::Bound::Included(&start) => start,
std::ops::Bound::Excluded(&start) => start,
std::ops::Bound::Unbounded => std::$float_type::MIN,
};
let mut right = match rng.end_bound() {
std::ops::Bound::Included(&end) => end,
std::ops::Bound::Excluded(&end) => end,
std::ops::Bound::Unbounded => std::$float_type::MAX,
};
assert!(
eps > 0.0,
"Allowable margin of error must be a positive number."
);
if left >= right {
return None;
}
if is_ok(right) {
return Some(right);
}
if !is_ok(left) {
return None;
}
while (right - left) > eps {
let mid = right - (right - left) / 2.0;
if mid <= left || right <= mid {
return None;
}
if is_ok(mid) {
left = mid;
} else {
right = mid;
}
}
Some(left)
}
/// If `is_ok` is monotonically increasing,
/// returns the smallest floating point number `x`
/// that satisfies `is_ok(x) = true` as the value of `Some`.
///
/// If `is_ok` is monotonically decreasing,
/// returns the largest floating point number `x`
/// that satisfies `is_ok(x) = true` as the value of `Some`.
///
/// Returns `None` if no such floating point number exists in both of the above cases.
/// This includes the case where the absolute error cannot be determined
/// to be less than or equal to `eps`.
///
/// # Arguments
///
/// * `rng` - Domain of function `is_ok`.
/// * `is_ok` - Monotonic function.
/// * `eps` - The allowable absolute error. It must be a positive number.
/// * `dec` - Represents that `is_ok` is a monotonically decreasing function if true,
/// or a monotonically increasing function if false.
///
/// # Examples
///
/// ```
/// use atcoder8_library::binary_search::binary_search_with_f64;
///
/// let is_ok = |x: f64| { x.powi(2) >= 400.0 };
/// let ans = binary_search_with_f64(0.0..100.0, is_ok, 1e-6, false).unwrap();
/// assert!((ans - 20.0).abs() <= 1e-6);
///
/// let is_ok = |x: f64| { x.powi(2) >= 400.0 };
/// assert_eq!(binary_search_with_f64(0.0..10.0, is_ok, 1e-6, false), None);
///
/// let is_ok = |x: f64| { x.powi(3) <= -8000.0 };
/// let ans = binary_search_with_f64(-100.0..0.0, is_ok, 1e-6, true).unwrap();
/// assert!((ans - (-20.0)).abs() <= 1e-6);
/// ```
pub fn $fn_name<R, F>(
rng: R,
is_ok: F,
eps: $float_type,
dec: bool,
) -> Option<$float_type>
where
R: RangeBounds<$float_type>,
F: FnMut($float_type) -> bool,
{
if dec {
$fn_name_for_dec(rng, is_ok, eps)
} else {
$fn_name_for_inc(rng, is_ok, eps)
}
}
pub trait $trait_name: Sized + RangeBounds<$float_type> {
/// Performs a binary search on the domain specified by the Rust's built-in range type.
///
/// If `is_ok` is monotonically increasing,
/// returns the smallest floating point number `x`
/// that satisfies `is_ok(x) = true` as the value of `Some`.
///
/// If `is_ok` is monotonically decreasing,
/// returns the largest floating point number `x`
/// that satisfies `is_ok(x) = true` as the value of `Some`.
///
/// Returns `None` if no such floating point number exists in both of the above cases.
/// This includes the case where the absolute error cannot be determined
/// to be less than or equal to `eps`.
///
/// # Arguments
///
/// * `is_ok` - Monotonic function.
/// * `eps` - The allowable absolute error. It must be a positive number.
/// * `dec` - Represents that `is_ok` is a monotonically decreasing function if true,
/// or a monotonically increasing function if false.
///
/// # Examples
///
/// ```
/// use atcoder8_library::binary_search::BinarySearchWithF64;
///
/// let is_ok = |x: f64| { x.powi(2) >= 400.0 };
/// let ans = (0.0..100.0).binary_search(is_ok, 1e-6, false).unwrap();
/// assert!((ans - 20.0).abs() <= 1e-6);
///
/// let is_ok = |x: f64| { x.powi(2) >= 400.0 };
/// assert_eq!((0.0..10.0).binary_search(is_ok, 1e-6, false), None);
///
/// let is_ok = |x: f64| { x.powi(3) <= -8000.0 };
/// let ans = (-100.0..0.0).binary_search(is_ok, 1e-6, true).unwrap();
/// assert!((ans - (-20.0)).abs() <= 1e-6);
/// ```
fn binary_search<F>(
self,
is_ok: F,
eps: $float_type,
dec: bool,
) -> Option<$float_type>
where
F: FnMut($float_type) -> bool,
{
$fn_name(self, is_ok, eps, dec)
}
}
impl $trait_name for RangeFull {}
impl $trait_name for RangeTo<$float_type> {}
impl $trait_name for RangeToInclusive<$float_type> {}
impl $trait_name for RangeFrom<$float_type> {}
impl $trait_name for Range<$float_type> {}
impl $trait_name for RangeInclusive<$float_type> {}
};
}
impl_binary_search_with_float!(
f32,
binary_search_with_f32_for_inc,
binary_search_with_f32_for_dec,
binary_search_with_f32,
BinarySearchWithF32
);
impl_binary_search_with_float!(
f64,
binary_search_with_f64_for_inc,
binary_search_with_f64_for_dec,
binary_search_with_f64,
BinarySearchWithF64
);
}
}