結果
| 問題 |
No.3074 Divide Points Fairly
|
| コンテスト | |
| ユーザー |
 atcoder8
|
| 提出日時 | 2025-03-29 16:16:31 |
| 言語 | Rust (1.83.0 + proconio) |
| 結果 |
AC
|
| 実行時間 | 17 ms / 2,000 ms |
| コード長 | 22,365 bytes |
| コンパイル時間 | 12,783 ms |
| コンパイル使用メモリ | 399,376 KB |
| 実行使用メモリ | 7,324 KB |
| 最終ジャッジ日時 | 2025-03-29 16:16:49 |
| 合計ジャッジ時間 | 16,505 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 42 |
ソースコード
use binary_search::BinarySearchWithI64;
use proconio::input;
const C_MAX: i64 = 2 * 10_i64.pow(10);
const RANDOM_GRADIENTS: [(i64, i64); 100] = [
(48669, 30970),
(31724, 7191),
(82974, 65275),
(-28495, 22663),
(-35842, 51621),
(86168, 15183),
(-12505, 2071),
(88213, 66127),
(48761, 175),
(-62041, 17607),
(31495, 83617),
(90725, 61858),
(36434, 67373),
(1784, 31351),
(19958, 71181),
(-42072, 32075),
(2269, 2259),
(13455, 1241),
(22621, 1667),
(391, 18759),
(48844, 92833),
(36387, 1540),
(77348, 25301),
(-25530, 48917),
(-49593, 43666),
(-8881, 79738),
(17190, 27373),
(-477, 3923),
(17377, 27295),
(6693, 1259),
(7309, 31792),
(12029, 14066),
(-31287, 10754),
(4869, 8741),
(13081, 1032),
(-2783, 174),
(-22793, 45625),
(-5141, 45712),
(-40759, 87222),
(-16259, 72397),
(-36453, 43822),
(75913, 58614),
(-1624, 1795),
(-41543, 34669),
(-1437, 74219),
(12919, 9831),
(66077, 23058),
(-45390, 27589),
(-69287, 5227),
(1539, 45865),
(-18171, 173),
(49890, 89243),
(-16343, 15144),
(-74977, 82741),
(95189, 59035),
(-2999, 72080),
(12141, 19436),
(-4854, 9187),
(57871, 48343),
(-1244, 40807),
(-20487, 659),
(-43177, 24149),
(93909, 44488),
(-64217, 66255),
(-7205, 14819),
(35754, 68891),
(3443, 79699),
(33866, 4099),
(-7469, 91005),
(26660, 15977),
(-71573, 17721),
(-44954, 14019),
(-31265, 47611),
(36208, 88749),
(-50689, 42871),
(-6633, 1064),
(10099, 29415),
(-31917, 42130),
(-10247, 6188),
(-2484, 9145),
(29098, 69519),
(-31279, 89989),
(23367, 55883),
(-33485, 10453),
(65496, 30899),
(-11226, 6605),
(-42965, 41187),
(17951, 12795),
(-7671, 2746),
(-35499, 85127),
(-27143, 24969),
(42451, 91097),
(-81163, 89637),
(82429, 27831),
(-31990, 42869),
(70573, 18345),
(-43329, 14797),
(-76451, 78063),
(-26891, 49905),
(-35743, 23898),
];
fn main() {
input! {
n: usize,
xy: [(i64, i64); 2 * n],
}
let find_solution = |gradient: (i64, i64)| {
let (a, b) = (-gradient.0, gradient.1);
let is_ok = |c: i64| xy.iter().filter(|&&(x, y)| a * x + b * y + c < 0).count() >= n;
match (-C_MAX..=C_MAX).binary_search(is_ok, true) {
Some(c) if xy.iter().all(|&(x, y)| a * x + b * y + c != 0) => Some((a, b, c)),
_ => None,
}
};
let (a, b, c) = RANDOM_GRADIENTS
.into_iter()
.find_map(find_solution)
.unwrap();
println!("{} {} {}", a, b, c);
}
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
);
}